Нужен работающий sendmail либо его аналог. Когда выполняется mail(), то php грубо говоря в консольке выполняет команду: mail -s "Test Subject" user@example.com
На бесплатном его выключают чтобы спам не слали. Можно прикрепить например домен к яндексу и слать через через яндекс smtp:
i-leon.ru/smtp-php/, это способ без лишних телодвижений, недостаток - медленно будет идти посылка сообщения. Если платный хостинг, и рассылка через mail, то скорее всего придется еще заморочится c dkim, spf, dmarc, хотя некоторые и так это автоматом настраивают.
