These are bounce messages. Something is sending messages through your mail server, but the recipient is not accepting it, so your system generates a bounce message. Those bounce messages are being refused also, so they get "frozen" by the Exim MTA. You need to figure out where the messages came from originally and stop the flow of those unauthorized messages.

Once you find out what process is being used to send those messages through your system, you can take steps to prevent them, assuming they are not valid messages to begin with. What steps you take will very much depend on what you find.

Frozen messages are of no use in the Exim queue. You can remove all these to reduce queue list. The following command will remove all the frozen emails:

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

or

exiqgrep -z -i | xargs exim -Mrm

If you want to remove frozen email older than a particular hour, for example, 24 hours:

exiqgrep -zi -o 86400

86400 stands for 24 hours in seconds. That can be changed accordingly.

Also, frozen bounces can automatically be purged by Exim by setting the configuration option:

ignore_bounce_errors_after to a suitable value, e.g.
ignore_bounce_errors_after = 12h

This will automatically remove those bounce errors after 12 hours.