I have formatted my secondary machine many times, and machines for other people, but I have never had to reformat my own primary machine, a P-II 400 with W-98.
I do clean it out rather frequently, but I have never had a serious problem with tjhis machine. However, awhile back I installed COPERNIC DESKTOP SEARCH, then removed it because I did not like the Toolbar additions. However, I believe it was this program that left a small problem that will probably require a reinstall of Windows. When my system boots, I have 2 each instances of QuickLaunch and another Toolbar I use, and the problem is not in the registry.
I will probably just save the current registry backup, Deletree C:\Windows, Rename C:\Program Files then re-install Windows, put back the old registry, delete the new C:\Program Files, and then rename the "renamed" C:\Program Files back to C:\Program Files. It should save me a lot of reinstall time since I probably have 6 or 7 hundred programs and utilities installed in my primary system.
Until then I just delete the duplicate toolbars during bootup.