Intermittent Slowdowns

My cousin asked me to help her with her computer problems. Her computer is a Toshiba Satellite, running Windows XP Media Edition, with AOL dial-up internet connection; with Intel Celeron M CPU 420 with 1.6 GHz, and 512 RAM
A week ago it was working fine. Then, for no apparent reason, it became slower than molasses and basically non-functional.
Ran a Malware Bytes scan and discovered a virus that disconnected her Norton Internet Security.
Thought this would fix things, but computer still extremely slow (eg 2-3 minutes to pull up Windows Explorer for a file list).
Assumed more viruses not detected, so did the following scans:
Kaspersky Virus removal tool, VIPRE Rescue, ESET online scanner. Discovered nothing.
During this time, sometimes the computer would work like clockwork; other times, for no apparent reason it would go back to semi-non-functional slowness (note: in Safe Mode it always works fine; no slowdowns). Thought likely problem was now Norton and AOL (perhaps virus had messed with these.)

I then deleted and installed new Norton (she had 3 copies of NIS 2005 plus one of Norton Go Back); deleted a McAffee Scanner (?? must have come with some toolbar or something); deleted AOL and installed new version of AOL, updated IE and JAVA.
At completion, all worked well. Connected to internet via ethernet -- no problems with browser or internet surfing). Then, for no apparent reason, the computer slowed down again (same non-functional speed). After slowdown a Windows update appeared so I installed and hoped that the slowdown was due to downloading. Still uneasy, I decided to run ComboFix to be sure. AFter, computer ran fine. But to be sure, I thought I'd check for a hardware problem. I ran a Memtest (4 passes) and HD Tune. Both showed no problems. I told my cousin to come pick up her computer. As you guessed, when I turned it on, the computer was back into its non-functional slow mode. I kept hoping this was a Windows update slowdown, but it was not. Then went into safe mode and it worked like clockwork. Turned it on again in normal and it continued to work like clockwork.

OK I am totally stumped, but after reading on your site, I am now thinking maybe this is software.
What do you think the problem might be and what tests or scans if any should I run?