Agregale el encoding (Content-Transfer-Encoding: 8bit), y fijate. Si te da lo mismo, fijate en los head, a ver que te esta mandando realmente.
Otra es que hay servidores que tienen problemas con el \n\r, asi que te aconsejo hacer algo como:
$mail_from = '
[email protected]';
$headers = "From: ".$mail_from."
Return-Path: ".$mail_from."
Reply-To: ".$mail_from."
MIME-Version: 1.0
Content-Type: text/html; charset=\"iso-8859-1\"
Content-Transfer-Encoding: 8bit";