Kód:
Mail("komu@domena.cz", "predmet", "nejaky text zpravy", "Content-Type: text/plain");
takhle nejak to používám já a problémy s tím nemám, příjde to vždy (webzdarma). Hlavičku nastavuju akorát ten Conten-Type na text/plain, pže mi to pak můj homemade klient nezobrazuje. Pokud zádáš ještě hlavičku From: xxx@xxx.cz tak místo třeba info@wz.cz bude tebou zadaná adresa.
Taky záleží na tom, jak je to s podporou fce Mail u poskytovatele web prostoru.

tady to máš všechno popsané:
http://cz2.php.net/function.mail