Just thought i'd update the thread incase anyone else is having problems:
It turned out the server had a site with a mailer on it who was sending out thousands of spammy emails (should get round to setting up that..) and as such the mailq was filled up with 65 odd thousand messages. I deleted them all with postsuper -d ALL and it's right as rain again.
To find out, have it running and use
to see a tree of commands being ran, and see what's running under the server.php process. That should give you a good hint to see what's going wrong.