Hm, that sounds a lot like (or just like) the one I removed from my friend's machine recently.

His wife got it by visiting a rigged classic rock radio web site using Internet explorer.

In his case the startup was slow enough that before the malware loaded I was able to install and run process explorer (a task manager replacement) and noticed a weird looking .exe with a random file name running, using up all the cpu/ram.

Deleted that and everything went back to normal.

These programs are usually dug in deeper than that though.