I think GMail is the best engineered free mail offering out there, but there are a couple of issues with it:
- You don't own the data, and you have no legal recourse if they mess up or lose your data;
- You are giving Google an awful lot of your personal data to analyse how they please, and they know more about data mining than anyone else.
Basically, I think you have to trust Google a fair bit to use GMail. That said, they are less likely to lose your data than most people will be with a self-administered machine.
web.de offer a free email service with both POP and IMAP, which I have used without problems for years (as well as a GMail account, and an email server i run myself).