Veamos, si el email es en formato HTML, los saltos de linea tienen que ser saltos de linea HTML, es decir, <br>.
De todas formas, si el email es un HTML, ¿por que no pruebas a usar entidades HTML? Mira la funcion
www.php.net/htmlentities .
Ademas, eso creo que solucionaria tu problema con el webmail. El web mail te falla porque el charset lo define la pagina web que muestra el mensaje (aunque un webmail deberia tener eso en cuenta).
Suerte.