Ya lo resolvi :]
Agregue estas lineas:
Cita: $message = urlencode($message);
$message = ereg_replace("%5C%22", "%22", $message);
$message = urldecode($message);
$message = stripslashes($message);
Y se resolvio, ya llegan correctamente los mails. Pero otra duda, para no abrir otro tema,
¿Como puedo hacer que lleguen a la bandeja de entrada de hotmail? Siempre llegan al correo no deseado.