If it thinks the file is there, but write protected, then the file usually should still be there. I would open an explorer window and click tools then file options and click view Select the bullet for Show hidden files and folders and then take the check mark out of Hide Protected operating system files (Recommended).
Yes this is very simple but we need to start somewhere. If this doesn't work try renaming the directory and see what happens. If you get no error try adding in the .exe file and renaming the directory back.
Update 9/21/11 10:15
If the folder can't be renamed as well, then you have a bit of a bigger problem, something is locking down the folder/directory. Next I would try it in safe mode. What is it that you are trying to uninstall? What version of XP is this? Is this issue on one machine or many? And what is the machine being used for? (business, general home use, ...)
If you are still having issues I would run the windows installer clean up utility on it, then in the registry go to HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Uninstall and find any references to the program and delete those folders. Like always make sure you backup the uninstall directory before editing in it, that why if you screw up you can undo your changes.