Есть несколько опций:
1. Настроить полноценный Mail сервер на этом сервере.
2. Использовать работающий Mail сервер, в настройках SPF (обычно это TXT запись) разрешить отправление с IP этого сервера: ip4:123.123.123.123
Замените 123.123.123.123 IP на адрес сервера. В результате должно быть типа:
v=spf1 a:vash.domen ip4:123.123.123.123 -all
3. Как указал
Дмитрий - использовать SMTP авторизацию для сайта. Это самый правильный метод.
4. Настроить SMTP пересылку на уровне сервера (у вас должны быть права root) - я использую SSMTP для этого.