I never tried deleting all private messages for everyone. But the messages are stored in three tables. You could truncate all three or in phpmyadmin empty all three.
Of course I would make a backup just in case.
Blue Man Group There is no such thing as stupid questions. Just stupid answers