Azzido (Вчера / 08:51) так что хост здесь не при чем, тело письма должно быть правильно кодировано
mail("кому@домен", "ололо", "пыщьпыщь", "From: откуда@доменr\n" ."Reply-To: откуда@домен\r\n" ."X-Mailer: PHP/" . phpversion());