I was unlucky to get this message and spent a day debugging. So here is the wisdom so far missing from the Internet:
1) The message " Windows could not start because the following file is missing or corrupt: <windows root> \system32\hal.dll Please reinstall a copy of the above file. " pops up if NTLDR cannot load the HAL.DLL
2) Usually the problem is caused by a corrupted boot.ini (pointing to a wrong device) or a broken / absent HAL.DLL. There is plenty of advice on Internet on what to do. This page is not about this trivial case.
3) My $0.02: if everything in boot.ini and HAL.DLL seems to be OK, the problem might be in the location of the HAL.DLL file. According to the documentation, the NTLDR uses BIOS INT 13 to read the disk if multi() is specified in boot.ini. In my case, apparently BIOS was broken just enough to be not able to reach to the end of my 260GB disk, where HAL.DLL was relocated by some unwitting disk utility. I solved the problem by just defragmenting the disk (after booting from another drive), some other folks might need to delete crap in the beginning of their disks and defragment.
4) Good luck!