Over the last few months on one of my Linux computers, the mail transfer agent, exim has been trying to return email back to certain people to tell them it can't deliver the messages. But because these people are spammers their addresses don't exist so the messages can't be returned. As a result a huge mail queue has been built up of 'frozen' messages.

To get rid of them, log in as root and enter the following command:

 exim -bpr | grep frozen | awk {'print $3'} | xargs exim -Mrm

Another useful command is the following one that reports how many frozen mails are in the queue:

exim -bpr | grep frozen | wc -l 

And finally this command reports how many mails (frozen or not) are in the queue:

exim -bpr | grep "<" | wc -l 

Thanks to this thread for this invaluable advice.

Red Hat Certified Technician & Engineer (RHCT and RHCE) Training Guide and Administrator's Reference