GuardianAngel: If you log off and relog in on occasion, that should fix things. I have a few hundred PMs, but I know some people (ahem) have thousands.
What about limiting the maximum number of PMs each member can have. The oldest gets deleted when you go over the maximum. That forces members to be more organised about their PMs and delete the ones that they do not need to keep. The only problem is that unethical members can force another member's PMs to be deleted by sending them a stack of PMs at once. I imagine the threat of banning such members would keep it under control.
A refinement to that is an archiving feature. Allow members to archive PMs. You then have two databases of PMs: The core PM database that is queried whenever a member accesses the PMs. It can be kept lean and mean with a maximum limit per member. Then all other PMs are on the archive database that is only queried when someone selects the option to look at their archives. As most people are only checking recent PMs the lean and mean core db will be good for most situations. However, the archive of all their messages are there is someone needs to go back and check something.
I don't know how feasible these suggestions are, but I hope they might be useful.