I had the very same problem this morning and was pulling my hair out until I had a brainwave... and it acually works!
Before I tell you how to do it, I have to say i'll accept NO responsibilty for anything that may oocur when your doing it - but I can confirm that it was successful on my PC.
For some reason the uninstall file does seem to go missing when the uninstall process crashes! And the problem with reinstalling SQL Server means it creates a NEW uninstall file for your NEW instance with NEW folder locations!
I had a named instance on my PC, but it will work on default installations.
What you need to do is: -
Navigate to "C:\Program Files\Microsoft SQL Server"
In here should be a few folders one called "80" and one called "MSSQL" - this is your installation of SQL, if when you first installed SQL you created a named instance there should be a folder like this, "MSSQL$?instancename?", obviously where i've put instance name is whatever you called YOUR instance.
In order to uninstall SQL, you need to rename the folders starting with "MSSQL". DO NOT touch the folder named 80.
Re Run the install disc BUT, make sure you name the SQL Server exactly the same as the one you want to uninstall. (i.e. If it was a default install, leave it as default. If it was a named instance, name the instance exactly the same).
Then restart your PC.
At this point, go to Start -> Settings -> Control Panel -> Add Remove Programs.
Remove the SQL installation you just installed (sounds mad, but because you named it the same as the corrupt one, it uninstalls the SAME files!)
If this uninstalls completely, and sucessfully:
Before you reboot, go to "C:\Program Files\Microsoft SQL Server"
And completely remove the "Microsoft SQL Server" from program files.
Then reboot your PC, and SQL Server is gone!