I've had very good success with GMX <http://gmx.com/>. GUI is very similar to desktop e-mail clients and spam filters are very good. (I still think Yahoo's spam filters are the best.)
I didn't know a whit of German, but they had made a half-assed attempt at an English translation, which I actually made do with, because it was so awesome otherwise (superb interface for its time, POP3 access, open SMTP which didn't seem to get raped by script kiddies - and all this for free). The translation was missed out at certain points, but at least it made me look up words like ubernehmen and abbrechen.
Then one sad, SAD day, after I'd been a steadfast user for nearly 3 years, they sent an email to everyone saying they were shutting down the half-English site completely, and leaving only the German interface up. It was a really nice email too, in which they hoped the users would take this as an opportunity to learn a bit more German. Sadly I was just about finishing up with high school then and headed off to college, and didn't really have the time or energy to tinker with learning a new language as well, so it was with a heavy heart that I bid farewell to my beloved gmx.net account, after downloading all of my email into (one of the more under-rated Windows email clients of its time) Calypso.
Just created an account there again for old times sake, but I wasn't able to get <firstname>@gmx.com this time :(
</nostalgia>