Ho appena finito di risolvere lo stesso problema: nel mio caso si trattava di una impostazione del server. Infatti su sistemi Unix OsCommerce sfrutta le funzioni di sistema (sendmail o php mail) per inviare i messaggi, per cui se non è attiva questa opzione (o se c'è qualsiasi filtro) non funzionerà mai.

Sei in hosting condiviso o dedicato, o è un server personale? Sei su Linux o su Windows?