OK, people. 47 views, but not one post in less than 12 hours. It seems I'm not the only one with this problem!
However, I seem to have stumbled upon the cure (at least in my case).
I should have noted that one of the problems I had was that my Microsoft Wireless keyboard stopped working when the trouble started. I uninstalled the drivers for it, and reinstalled it, but it stopped working again in a few hours.
Here's what this trojan did: It installed a piece of hardware (not really, but Windows thought it was installed), and installed the "driver" for it. This was how I got reinfected when I replaced the drivers for the keyboard (which may have been the "payload" from the virus?)
I'm probably not making much sense, I'm so excited about getting it fixed (at least it's fixed now. I'll let you know tomorrow if it stays fixed.)
Steps to fix my problem:
1. Downloaded Combofix.exe from http://download.bleepingcomputer.com/sUBs/ComboFix.exe
(don't download from combofix.org -- the program warns that this site is not affiliated with the program.)
2. Closed all IE windows.
3. Disabled my antivirus software.
4. Ran Combofix. It had to install Microsoft's Recovery Console, so I let it.
5. It found evidence of a rootkit infection (esellerateEngine.dll and c:\windows\system32\drivers\kbdhid.sys) and "Kitty had a snack." The kbdhid.sys file is a legitimate Windows file, so I'll probably have to reinstall that with my keyboard drivers.
6. Upon reboot, it seemed to fix the Google redirect issue.
I will note that upon reboot, Windows tried to install SmartSound Quicktracks plugin, which I've never had before. It failed, and I went to Add/Remove programs and uninstalled it from there (it hadn't been there before).
I'm keeping my fingers crossed, but this is the longest it's gone without redirecting. Usually, upon reboot, it started redirecting within two or three clicks.