Problema com função Mail()

Segui as recomendações da Locaweb (meu servidor), mas ainda assim está dando erro.

As variáveis foram definidas para teste, pois são recebidas a partir de um flash, logo eu não conseguiria testar apenas a págin PHP.

<?php

/ Medida preventiva para evitar que outros domínios sejam remetente da sua mensagem. /

if (eregi('tempsite.ws$|locaweb.com.br$|hospedagemdesites.ws$|websiteseguro.com$', $_SERVER[HTTP_HOST])) {
 $emailsender='luan@dx8.com.br'; // Substitua essa linha pelo seu e-mail@seudominio

} else {

 $emailsender = "dx8@dx8.com.br" . $_SERVER[HTTP_HOST];
 //	Na linha acima estamos forçando que o remetente seja 'webmaster@seudominio',
 // você pode alterar para que o remetente seja, por exemplo, 'contato@seudominio'.
}

/ Verifica qual é o sistema operacional do servidor para ajustar o cabeçalho de forma correta. Não alterar /
if(PHP_OS == "Linux") $quebra_linha = "\n"; //Se for Linux
elseif(PHP_OS == "WINNT") $quebra_linha = "\r\n"; // Se for Windows
else die("Este script nao esta preparado para funcionar com o sistema operacional de seu servidor");

// Passando os dados obtidos pelo formulário para as variáveis abaixo

$assunto = "Contato por meio do Site VP";
$empresa = "LRO ";
$depto = "Desenvolvimento";
$nome = "Luan";
$telefone = "1234-5678";
$endereco = "Rua x, 0 - apto 3 bl 1";
$bairro = "Bairro";
$cidade = "São Paulo";
$uf = "SP";
$cep = "01234-567";
$email = "rodrigues.luan@hotmail.com";
$mensagem = "Mensagem teste!";

/ Montando o cabeçalho da mensagem /

$headers = "MIME-Version: 1.1".$quebra_linha;
$headers .= "Content-type: text/html; charset=iso-8859-1".$quebra_linha;

// Perceba que a linha acima contém "text/html", sem essa linha, a mensagem não chegará formatada.

$headers .= "From: ".$emailsender.$quebra_linha;
$headers .= "Reply-To: ".$email.$quebra_linha;

// Note que o e-mail do remetente será usado no campo Reply-To (Responder Para)

/ Montando a mensagem a ser enviada no corpo do e-mail. /

$mensagemHTML = '<P>Esse email é um teste enviado no formato HTML via PHP mail();!</P>
<P>Aqui está a mensagem postada por você formatada em HTML:</P>
Empresa: '.$empresa.' <br>
Departamento: '.$depto.' <br>
Nome: '.$nome.' <br>
Telefone: '.$telefone.' <br>
Endereço: '.$endereco.' - '.$bairro.'<br>
'.$cidade.' / '.$uf.'<br>
'.$cep.' <br>
<p><b><i>'.$mensagem.'</i></b></p>
<hr>';

/ Enviando a mensagem /
//Verificando qual é o MTA que está instalado no servidor e efetuamos o ajuste colocando o paramentro -r caso seja Postfix
if(!mail($emaildestinatario, $assunto, $mensagemHTML, $headers ,"-r".$emailsender)){ // Se for Postfix
$headers .= "Return-Path: " . $emailsender . $quebra_linha; // Se "não for Postfix"

	mail($emaildestinatario, $assunto, $mensagemHTML, $headers );
}

/ Mostrando na tela as informações enviadas por e-mail /

print "Mensagem <b>$assunto</b> enviada com sucesso!<br><br>
De: $emailsender<br>

Para: $emaildestinatario

<p><a href='".$_SERVER["HTTP_REFERER"]."'>Voltar</a></p>"
?>

Segue o ERRO:

PHP Warning: mail() [function.mail]: SMTP server response: 503 RCPT first (#5.5.1) in E:\home\dx8\Web\VP\imagens\formulario.php on line 54 PHP Warning: mail() [function.mail]: SMTP server response: 503 RCPT first (#5.5.1) in E:\home\dx8\Web\VP\imagens\formulario.php on line 56

As linhas 54 e 56 são as de envio de email

54 if(!mail($emaildestinatario, $assunto, $mensagemHTML, $headers ,"-r".$emailsender)){ // Se for Postfix

55 $headers .= "Return-Path: " . $emailsender . $quebra_linha; // Se "não for Postfix"

56 mail($emaildestinatario, $assunto, $mensagemHTML, $headers );

57 }