How to clean a virus/malware/trojan that seems to generate “memory could not be” read/written error on all?

If I login into XP the regular way, every program generates an application error of the genre "memory could not be written" or "memory could not be read".
If I login through the recovery console, this does not occur. All programs and executable work as normal.
Every virus, spyware, malware, trojan scan says the system is clean. I also ran a registry cleaner.
How do I fix this problem without formatting and reinstalling XP?