нужно, чтобы на сервере был sendmail демон ( qmail ). Он будет обрабатывать очередь. php.net/manual/en/function.mail.php ищите на странице 'queue', там есть несолько идей.
Может, делать что то типа планировщика задач, в который добавляется отправка письма со всем необходимым, а он выполняется отдельно от скрипта в какой то период времени.
Это всё да. Но мне просто нужно отправить письмо. Один раз. Делать для этого планировщик не хочется. Достаточным будет обработать эту ошибку. Гугл молчит как партизан.
Вместо отправки, пишите письмо в json/xml файл или в БД. А по крону запускайте скрипт, отравляющий письмо. Если письмо отправится, удаляйте/перемещайте файл/запись.
Ещё очень красиво решается асинхронными задачами в Gearman.
Если vds на чем-то дебианоподобном — apt-get install exim4-base
или любой другой почтовый сервер, с которым работали.
Конфиги по-умолчанию (по состоянию на осень 2011) работали с настройками «из коробки» без проблем.