Удалить все замороженные сообщения из очереди

Один из вариантов, в зависимости от имеющихся утилит

Exim

exipick -zi | xargs exim -Mrm
exiqgrep -zi | xargs exim -Mrm
exim -bp | awk '/^ *[0-9]+[mhd]/{print "exim -Mrm " $3}' | bash

Sendmail

mailq | wc -l
find /var/spool/mqueue -type f -exec rm -f {} \;