OL2003 SP2 and cached mode?

Yes

How big his his mailbox?

Too big: 3 GB I need to work on getting him to reduce this even if it
isn't the cause of the problem, but it will make my argument better if I can
tell him it will solve this problem.

More importantly, how many items does he have per folder (e.g., how many
items in his inbox, or whatever he happens to be clicking on at the time)?
I don't mean in subfolders....just how many in each folder directly.

Good question. I'll ask to see if it's normally when he's working in a
specific folder or not.