Y que cabeceras HTTP usas en tu mail() ? .. tal vez no usastes/definistes que el e-mail que estás enviando es en formato HTML (eso se indica con una cabecera) . .así que tu cliente de correo entiende que es texto plano simplemente.
Puedes ver un ejemplo:
http://www.forosdelweb.com/f18/faqs-php-530600-post254350/
Un saludo,