I just helped a user where they had a virus that didnt delete the windows update service but instead corrupted its registry setting, so not even trying to delete it will work. Lets see if you have the problem as well.
In the registry go to HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\wuauserv
Are up able to view it or do anything with it or do you get an error?
Shane