The thing is telling me my PM folders are 92% full, despite the fact there are no messages in there, does anyone know how I can get it back down to zero?

I'm afraid I've got no idea what could be the problem at this time.. Though, have you checked the "Sent Items", maybe there're still messages hiding in there?

There were some, and that's taken it down to 70% which I still cannot get rid of

The following may seem a little harsh but if you really want to remove all your messages, you can always click the "Empty PM Folders"-button. I'm not sure if this action removes archived messages as well.