Just a quick & dirty hack to delete frozen messages for a single / some recipient(s)…

#!/bin/bash
#
# what are we searching for?
# (part of the email-address)
SEARCH="anyrecipient.tld"
#
# exim-bin
EXIM=`which exim`
#
# execute (frozen messages only)..
$EXIM -Mrm $(mailq | grep $SEARCH -B1 | grep frozen |cut -c 11-27)

Thanks to Mark -> this can be done a lot of easier if you want to kill all frozen messages:

exiqgrep -z -i | xargs exim -Mrm

If you want to do this only for some domains / email-addresses, use the first example.