I had the same problem as the thread starter. Window 7 64bit, removed the updater but the services and a bunch of junk still remained. In my case, I think I got it because I tried the Gmail Notifier which had a really old version of GoogleUpdate which didn't know how to uninstall.
Those 2 damn things lingered in my services list too. For some reason I couldn't find this topic and the "sc delete" anywhere from simple bing searches and anywhere, so instead I just manually deleted google program files, deleted the task scheduled items, and then ran a manual regedit search for "googleupdate" and "gupdate" and "gupdatem" and manually nuked every folder which contained ONLY obvious refererences of being connected to google update (ie referencing GoogleUpdate, the exe, etc). At some point it must have broke the services, since both services was giving me multiple errors whenever I tried to do them. The description for them failed (2) and then one that prevented me from even right clicking them for properties (error 1058). Restarted and then all was good!