|Firstly, it's not "nltdr", it's "ntldr".|
Secondly, it belongs at the root of your C: drive (or system drive, depending on your configuration). However, it may be hidden, as system files often are. To show hidden system files, open My Computer and click the Tools menu (at the top), then select Folder Options. Click on the View tab, and scroll down to Hidden files and folders, selecting Show hidden....
Just below that, remove the check from Hide protected ......
You should now be able to see NTLDR at the root of C: drive.
If you have had a particularly nasty virus/malware, it would probably pay to turn System Restore off, then back on to remove all restore points. Some malware/viruses have been known to hide in restore points, only to keep re-infecting the machine.
Have you tried downloading and running the XP Winsock repair?
There are a number of repair scripts available from Doug Knox's website (for repairing the different file associations and other Windows defaults). Look through the list of fixes and download/run any that sound like they'd be relevant.
When you try to re-install (via USB), make sure you delete the current C: partition and create a new one from scratch (follow the prompts during install). Often, I've found that remnants from a previous install will cause the sort of problems you mentioned (NTLDR missing, HAL.dll missing or corrupt, etc.). Even re-formatting an existing partition has given me this problem before (only with XP, no other version, so far), so be sure to use a newly created partition. This should allow you to install a new Windows, but unfortunately, doesn't help if you wanted to do a repair-install.
If a new install is an acceptable route for you, I'd try the new partition trick first. If you'd prefer to repair the existing installation, see if Doug Knox has a script that will help.
Please let us know if you found someone's advice to be helpful.