La soluzione è senza dubbio quella citata da Andrea.

Approfitto comunque per segnalare una libreria che ritengo sia molto importante per chi fa un uso particolarmente intenso della funzione mail utilizzandone molte sfaccettature: http://phpmailer.sourceforge.net/