Mail() PHP funciona em tudo menos na locaweb

Olá,

É o seguinte, eu tenho um script de email php que aparentemente funciona normal, ele envia, e recebo normalmente, mas precisei fazer um mesmo código dessa para enviar para um email da Locaweb e não chega la!

Eu pesquisei e vi que tem algumas regras la na Locaweb e mesmo assim fazendo tudo o que eles pedem não chega.

O código funciona normalmente, menos la...algume saberia o motivo disso?

aqui o meu código:

<?php
// Destinatario do email
$destinatario = "email@destinatario.com";
// Remetente do email
$remetente = "email@remetente.com";
// Recebe os dados e guarda nas vareaveis

$nome = $_POST['nome'];
$email = $_POST['email'];
$ddd = $_POST['ddd'];
$telefone = $_POST['telefone'];
$assunto = $_POST['assunto'];
$mensagem = $_POST['mensagem'];

// Monta o corpo do email

$mensagem_corpo = "Nome: ".$nome."\n";
$mensagem_corpo .= "E-Mail: ".$email."\n";
$mensagem_corpo .= "Número Telefônico: "."(".$ddd.")".$telefone."\n";
$mensagem_corpo .= "Assunto: ".$assunto."\n";
$mensagem_corpo .= "Mensagem: ".$mensagem."\n";
$mensagem_corpo .= "Email enviado pelo formulario do site www.site.com.br"."\n";

// Monta o cabeçalho do email

$headers = "MIME-Version: 1.1\n";
$headers .= "Content-type: text/plain; charset=iso-8859-1\n";
$headers .= "From: $remetente\n";
$headers .= "Return-Path: $remetente\n";

// Função PHP que faz o envio do email
if(mail($destinatario, $assunto, $mensagem_corpo, $headers, "-r".$remetente)){

	echo"<script type='text/javascript'>alert ('E-Mail enviado com sucesso');</script>";
	echo"<script type='text/javascript'>location.href = 'javascript:window.history.go(-1)';</script>";

}else{

	echo"<script type='text/javascript'>alert ('Falha no envio do E-Mail');</script>";
	echo"<script type='text/javascript'>location.href = 'javascript:window.history.go(-1)';</script>";
}
?>