qmail возвращает все письма как “обработчики permanentfail”

Это - случайно сервер Plesk? Существует горстка сообщений о найденном через поиск с помощью Google. Вот тот, подразумеваемый, зафиксируйте:

/usr/local/psa/admin/sbin/mchk --with-spam