As far as I can tell from experience, you don't have to reformat when changing video card even from ATI to nVidia or vice versa. However I think if you really want a "clean" running system then reformat would most likely be the best option. I've tried those driver cleaner softwares in the past, but quite honestly I felt that they just never managed to clean everything down as clean as if you're actually never installed those driver in the first place.
Actually, the drives are at that point contaminated on an atomic level. Best bet is to just buy some new SSDs at that time and send the old, contaminated ones to me for proper recycling/disposal.
Why do you feel that way? It's not like graphics drivers are performing voodoo on your Windows installation and are completely hidden.