From TechRepublic:
Not able to remove or uninstall an application in Windows XP using either the Uninstall option or the Add/Remove Programs tool? Try using the Windows Installer CleanUp Utility. As long as you installed the application using the Windows Installer, this utility will remove all the folders, files, registry keys, and entries from your system and allow you to start over with a clean slate.
I haven’t tried it, but it sounds very promising. Check it out…