It has as much to do with the number of PMs as it does users. I had 4,000+ messages between the Saved, Received and Sent folders and got those horrible delays. When I just deleted all but a couple hundred, the speed was back to normal.
I have one user with 9,000 messages between the folders - his page has to be really slow.
If I get some time, I'll play around with it; but even one query instead of the three is going to have the same delay because its the first query that took 96% of the time.
