Mail ist überhaupt problematisch, zumal man im Mailclient auch noch eine Standardcodierung einstellen kann, die verwendet wird, wenn der header nicht korrekt angeben ist (meiner ist z.B. immer utf-8 wenn nicht anders angeben).
Du könntest versuchen voir dem Versand mit
http://us1.php.net/manual/de/function.htmlentities.php zu arbeiten, was dich aber von einer korrekten Headerangabe aber nicht befreit.
utf8_encode()/decode() sind auch noch Hilfsmittel die du zu Rate ziehen kannst
Dein blaues Wunder wirst du dann sicherlich erleben, wenn du deine Mails in Outlook, Thunderbirs und einem Androiden testest. Das wird dir den letzten Nipf rauben....
good luck