Personally I for once side with Plusnet on this issue.
They've made no claims to offer storage of any kind. I don't use plusnet email for the very reason that they've had disasters with customers emails in the past. I wouldn't trust them to look after it.
What I do use is Yahoo! mail. They DO claim to offer storage (in the GB's) where you can keep virtually unlimited emails. Google are the same. Both Yahoo and Google are slugging it out in the email wars to try and cling onto their users. Therefore they're both trying to offer the very best service possible. Plusnet are only interested in taking money from you and giving you basic services. They're not trying to be a winning free service provider like Yahoo or Google who rely on free users to gain advertising revenue.
Downloading emails to Outlook express from Plusnet is a good way forward. Then you can back up the mailbox folders on another drive - even a thumbdrive!
It really isn't hard to take precautions against this sort of thing. I know thats no help now but maybe it will help you to protect yourself in the future.
I need a new signature... i'm bored of the old one!
