Exim4 в Debian Lenny идет с отключенной проверкой SPF [1]. Задействовать эту замечательную штуку можно пересобрав пакет (это не Debian-way, так что этот способ отбрасываем сразу) или сделав финт ушами, описанный ниже.