Pues sólo cambia el orden de esta forma:
Código PHP:
$contenido = "su Nombre------->:".$_POST["nombre"]."\n";
$contenido .= "de la Ciudad de------->:".$_POST["ciudad"]."\n";
$contenido .= "Su Correo es----------->:".$_POST["mail"]."\n";
$contenido .= "Su Telefono es------->:".$_POST["telefono"]."\n";
$contenido .= "Contenido de su mensaje------>:".$_POST["mensaje"]."\n";
$contenido .= "el mensaje se escribio el ".$fecha;
Suerte