NTDLL.DLL is a core Windows file. It contains many string, integer and file functions, which is why it appears so regularly in error messages (ie as other APIs call its functions). Also, due to exploited vulnerabilities, it's been the subject of a number of hotfixes since XP SP1 (ie v5.1.2600.1106).
One *possible* solution is to ensure that you are using v5.1.2600.2180. If not, you can get it from
http://www.dll-files.com/dllindex/dll-files.shtml?ntdll Note this version is only for XP and is the version that comes with SP2. Backup your current version first.
Usual causes for "sudden" errors in NTDLL.DLL are a) uninstalling software that mistakenly removes registry entries related to the DLL (most likely the cause through removing the SP2 Res Fix) or b) spyware or viruses removing the actual file (most likely not the cause here though as you've confirmed that the file exists).
Nb, I have also found that problems with the file tend to be limited to AMD chip users.