Проблема довольно-таки тривиальна, однако, поскольку о причинах её возникновения периодически спрашивают у Яндекса и Google, а также на различных форумах, — решил «оставить это здесь» в виде заметки. Вдруг кому-нибудь пригодится?

Симптомы:
При попытке отправить письмо, например с помощью php функции mail(), на свеже-развернутом сервере с дефолтными настройками (например — Debian 6.0 LAMP от Hetzner) — письмо приходит, но с задержкой, а скрипт «долго думает», порядка 2-3 минут, и, если запущен не через PHP CLI, — может упасть с 504 Gateway Time-out.

Если проверить /var/log/mail.err или /var/log/mail.log — можно будет увидеть строчки, похожие на эти:

Jan  1 11:20:01 Debian-60-squeeze-64-LAMP sm-msp-queue[25056]: My unqualified host name (Debian-60-squeeze-64-LAMP) unknown; sleeping for retry
Jan  1 11:21:01 Debian-60-squeeze-64-LAMP sm-msp-queue[25056]: unable to qualify my own domain name (Debian-60-squeeze-64-LAMP) -- using short name

Это означает, что sendmail пытается определить FQDN (Fully Qualified Domain Name), однако не находит его.

Для исправления ситуации открываем /etc/hosts и вносим соответствующие записи, например:

127.0.0.1	localhost.localdomain	localhost
80.92.100.100	server.domain.ru	server

Меняем hostname и перезапускаем сервер:

$ echo "server.domain.ru" > /etc/hostname
$ reboot

После перезагрузки сервера, при наличии соответствующей директивы в /etc/init.d/hostname.sh, — сервер установит необходимый hostname.

Главное, чтобы hostname соответствовал или являлся алиасом существующему домену или localhost‘у.