<?
mail('мыло','проверка','проверк а','From:<мыло>');
?>

так отправляет?
Что за хост хоть... многие админы просто иногда при создании отключают почтовые ящики, а не саму функцию..