Apparently you can’t uninstall the desktop search if you installed it as another user as you get the error message “Google Desktop Search was installed on this machine by a different user, DOMAIN\Username. To uninstall Google Desktop Search logon as that user” This is not necessarily possible if the domain doesn’t exist anymore (and therefore you CANT log on as that user)
The funny thing is that if you enter the error message into Google it asks if you meant login and not logon. (and there are no results for either of the two options.
I’ve logged an error report with Google, so we’ll see how long it takes for some action on this.
Update Working instructions on How to manually uninstall Google Desktop are posted here.