Por lo pronto, no estás evaluando en ningún momento que se haya enviado o no. Tu ELSE lo que evalúa es si tiene algo en las variables recibidas, no si se está enviando el mail.
Código PHP:
if(mail($destino,$asunto,$mensaje,"FROM: $remitente"))
{header('Location: contacto.php?mail=enviado'); }
else
{ header('Location: contacto.php?mail=error'); }