From the email that google sent me, here is how to remove Google Desktop by hand:-
Thank you for your note. If you’re unable to uninstall Google Desktop
Search through Add/Remove Programs and/or “Start” > “Programs” > “Google
Desktop Search” > “Uninstall Google Desktop Search,” you can remove it
manually. To do so, edit the Windows system registry and then delete the
appropriate program files. Here’s how:

TO EDIT THE WINDOWS SYSTEM REGISTRY:
Note: editing the Windows registry is an advanced process. You may prefer
to contact your system administrator.

That said, you should be able to solve the problem by deleting the
following registry keys:

– Hkey_Current_User\Software\Google\Google Desktop
– Hkey_Local_Machine\\Software\\Google\\Desktop\\InstalledNTUserName
– Hkey_Local_Machine\\Software\\Google\\Desktop\\InstalledUserSID

Restart your computer so this change can take effect, and then remove the
program files for Desktop Search. Here’s how:

TO REMOVE GOOGLE DESKTOP SEARCH:
Open C:\Documents and Settings\USERNAME-THAT-NO-LONGER-EXISTS\Local
Settings\Application Data\Google\Google Desktop Search. Delete all the
files in this directory.

If you need further assistance, please let us know.

Regards,
The Google Team

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.