What are frozen messages?

Frozen messages are messages that Exim will no longer attempt to deliver. You can thaw the message with:
exim -Mt [ … ]

To remove all frozen messages:

exiqgrep -z -i | xargs exim -Mrm
To show frozen messages:
exim -bp | grep frozen
Freeze all queued messages from local user:
exiqgrep -i -f luser@localhost | xargs exim -Mf