Moin,
in Bezug auf Datenschutz ist imho http://www.privatdemail.net/ der "beste Anbieter".
Allerdings fährt Mensch wohl am sichersten, wenn der Mailserver auf dem eigenen Router läuft ;).
GMX finde ich persönlich gräßlich, wenn man ab und zu die Weboberfläche nutzt.
Zu dem werden meine Adressen dort beson ders gerne mit Spam beglückt.
Web.de ist allerdings imho aufgrund des geringen Speicherplatzes und dieser zeitlichen Begrenzung für das Abrufen von E-Mails inakzeptabel.
Ich habe u.A. bei der Domainfactory eine E-Mailadresse (zu einem bestehenden Webpaket), und das nutze ich am liebsten. Vieleicht ist dies für dich ja ne Alternative? Kostet dann zwar ein paar Cent im Monat, dafür hast Du aber eine Mailadresse die sich etwas abhebt (naja, auch nicht wirklich).
greetz