Does it remove all entries in component category (i.e. ESRI Mx Commands) and CLSID automatically? I don't think the registry entry in HKEY_LOCAL_MACHINE\SOFTWARE\Classes\CLSID and HKEY_LOCAL_MACHINE\SOFTWARE\Classes for the custom DLLs gets cleaned up.
I think unregistering the DLLs will still leave entries in the categories, so you'll still have some work to do to clean everything up. I've had a quick look before on how to do this programmatically but never managed to work it out so always ended up doing it manually.
Since guids do not change and number of component CLSIDs do not grow often, a simple semiautomatic approach would be to prepare .reg file to delete registry entries using regedit (by double-clicking reg file), see http://support.microsoft.com/kb/310516
To delete from the registry would seem to be the only way to do it if you've got a large number of machines. Shame there doesn't seem to be any inbuilt support for doing this. It's all too easy to get things into categories, but if you're not careful you can easily end up with a lot of garbage in there.
It was typical in VB6 to use the Package and Deployment Wizard to create installers for ArcGIS customizations. ESRI had a VS addin that would create a *.reg file that you could use to register all of your classes. To unregister all of the classes you would create a copy of this file and modify it to unregister (put a minus in front of all of the registry keys). After you create the installer for your new .NET version of the application, just have it merge this "unregister" file into the registry.