I'd rule out the possibility of virus/spyware infections first. Have a look through the threads in our Viruses, Spyware, and other Nasties forum for suggestions and directions on some of the procedures you can follow determine if malicious programs are part of the problem.

Nope, she's run SpyBot, Avast, and Norton Antivirus, all of which deleted several unwanted things.

But the problem remains.

There are many infections out there that the above programs cannot detect, or cannot properly remove. Given that system lags/slowdowns are often indications of "unwanted guest", I'd suggest that there's still a chance that the computer is not 100% clean.

Of course, there are definitely other reasons for slowdowns; does the behaviour only occur in Internet Explorer, or is it noticeable when working with other programs as well?

Only in Internet Explorer is there evidence of a slow-down. It's doesn't really seem to me to be an actual computer lag as much as it seems like it's loading some web content it shouldn't be. It's like the computer is sending or receiving some other information through IE that isn't related to whatever website she is on. The page loads quickly but the green loading bars at the bottom are still there (they fill the box - like when there is only one more thing to download -) and it acts as if the page is still loading.

Something that may be relevant: her laptop has wireless capabilities, could there be something with the wireless network software causing the problem?