After a complete uninstallation via the Add/Remove programs tab, apart from clearing the registry via 'regedit' you also need to manually delete your Ubisoft Folder from your Programs directory as well as your Modman Folder from your HDD Directory. There are leftover folders after an uninstall that explains the issue you are experiencing.
To clear the registry, via the start menu, hit run and type 'regedit'. Hit OK and navigate to HKEY_CURRENT_USER/SOFTWARE and find the Eagle Dynamics entry. Highlight and delete.
Do the same for HKEY_LOCAL_MACHINE/SOFTWARE and the Ubisoft entry. Highlight and delete.
Reboot.
This is how I do it on XP, I would think it's the same on Vista and Win 7