Unless you really, really, really need to save PMs because you are a closet hoarder, it might be a good idea to clean house on a regular basis.

If you insist on hoarding your private messages, an alternative to keeping them on the server is to export them as text/csv -- or even XML if you're sadistic like that -- and storing them locally. The function is easily accessed on your main Private Messages page.