Instead of Internet Explorer, use Mozilla Firefox (
http://ftp.mozilla.org/pub/mozilla.o...up%201.0PR.exe). The Clear All button in the options works well.
If you're using WinXP, right-click->Properties on the Taskbar, Start Menu tab, Customize button, Advanced tab, Clear List button.
I'm not sure if 3rd party software is really needed. If they clean really obscure registry keys, what are the chances that someone would know enough to look for them?