When you say you deleted the registry keys, are you talking about the ones under Run? You've probably already done this, but I usually have pretty good results by searching for the keys named Run, and then deleting anything under there that I don't recognize or don't want running. HP and Compaq machines have a few things in there that can't be deleted without killing Windows, though, (ask me how I know,) so be careful if you have one of those machines.
I did a few friends machines that way and found one was running a keylogger that sent all the info to an IP in China. It surprised me that it took so long for him to realize he had a problem.