Oh, and could people recommending Gmail etc please think about it....
The email account has got nothing to do with the email client. You could have a Gmail account set up inside Outlook Express, and it lose its information.
Yes, asking the server to keep a copy is a viable solution, but you must then manage your emails in two locations. If this was going to be done, sometimes using IMAP is a better alternative.
Also, having had a client get locked out of his own personal gmail account for 2 weeks... Gmail is not the infallible magic non-breakable email account people seem to think it is.
Bookmarks