cara ... aparentemente esta estrutura condicional esta certa ... e se a msg de envio com sucesso esta ok ... é que o papel de enviar a msg a funcao mail() fez corretamente, agora isso pode ser configuracao do seu servidor smtp ... tente se possivel testar este mesmo script em um servidor remoto ... if (mail($email_destino, $subject, $mensagem, $headers)){ echo "Sua mensagem foi enviada com sucesso"; }else{ echo "Ocorreu um erro."; }