This happens to me all the time in WinXP. If I have one Arduino attached and I have been programming then all is ok. If I use that same port for something else and then forget to plug in the arduino before trying to send a program, I get that error. Plugging the Arduino back in never works. The only way I've been able to clear it is to reboot. It has always gone away.
So I agree that it is an OS problem. You may have actually made it worse by clearing the registry. Try using another usb port. You may have to reinstall the drivers.