La mail() ritorna true ma il messaggio non parte? Oppure produce un warning o altro errore?

In ogni caso se il server è vostro sarà possibile spulciare i log di Qmail, ed eventualmente partire da lì