I think the charset should be ISO-8859-1. You may need to update the local setting of your server. You can do this in php with the setlocale() function. Here is a ling to functions page on php.net:
function.setlocale.php
I think you would want to set it like this:
setlocale(LC_ALL, 'de_DE@euro', 'de_DE', 'de', 'ge');
This is an example from the php page. If you are still having problems you should check in the email message to see if you can find the encoding or charset. It may have to do with your mail servers settings as well.