Before anyone jumps on to bash Vista (you know who you are), I had an XP system last week, with the same problem.
I tried removing viruses, spyware, services, registry entries, everything I could through a BartPE disc. The system wouldn't even log in using safe mode, or when I used my BartPE to make a new user. I even tried a windows repair install.
The customer wanted the system back quickly, so after a while of trying, I just backed up her data and reinstalled windows. At the time, I just wrote it off as a strange software corruption...but someone else reporting it within a few days makes me think we might see this a few more times.
If anyone else is running across this, have you been able to fix it?