Isn't that a bit too far? Uninstalling, delete whatever trace of IE, and reinstalling should fix it...
It's possible to uninstall Internet Explorer's user interface, but it's not possible to uninstall the components that do the actual work or reset their registry keys to their default states.
If Internet Explorer's uninstaller actually removed all of the software's components, then it would break any application that uses Internet Explorer's WebBrowser control to display web content. I'm not certain of what exactly the uninstaller does, but I think it only exists as a result of antitrust rulings against Microsoft for bundling Internet Explorer with Windows.
Actually, there is one other thing you can try before reinstalling Windows: performing a clean start-up; however, this will only help if the cause of the problem is an application integrating itself into Internet Explorer in a way that causes unexpected results.