El tema codificación ya pude resolverlo. Respecto al segundo punto, estoy utilizando la opción [URL="http://www.php.net/manual/es/book.mail.php"]mail[/URL] que me recomendaste. Este es el código que estoy probando para el envío, el cual se efectúa correctamente:
Código HTML:
<?php
$Name = "Prueba Mail"; //senders name
$email = $_POST ["email"]; //senders e-mail adress
$recipient = "salparadise.ar@..................."; //recipient
$mail_body = 'Nombre:' . $_POST ["nombre_completo"] . '\r' . 'Ciudad:' . $_POST ["ciudad"]; //mail body
$subject = "Subject for reviever"; //subject
$header = "From: ". $Name . " <" . $email . ">\r\n"; //optional headerfields
mail($recipient, $subject, $mail_body, $header); //mail command :)
?>
Nuevamente, gracias por tu ayuda.