After writing my last article, I started digging into my mail configuration and after doing a quick "mailq" noticed a lot of frozen messages in Exim's queue. After inspecting the logs and the mails themselves I noticed the problem was caused by a broken POP server I retrieve mails from periodically. A few days ago something went wrong on that server and all messages were marked as unread causing my fetchmail to re-fetch all of them (about 2.5K).
Now that my mail server is configured to do sender verification and a few very old mails came from domains or systems which are non-existent today about 50 mails ended up being frozen.
But how to remove all frozen mails from Exim's queue? I ended up using mailq | grep frozen to get a list of all messages (and more importantly their message IDs) and saved that to a file. I then wrote a minimalistic Python script attached to this article to delete all those messages. Consider the script a quick and dirty hack, but it might come in handy for some of you. Get it here.