I have read many sources on how to delete all / some messages from exim's queue. Though none of them work because of the huge exim queue I am deleting. In case there are more than a few hundred messages in the queue, bash's variables max size will be exceeded.

That's why I will divide the process and use a text file for storing the exim queue's messages:

First we will get all the message's IDs:

# exim -bp| awk '{ print $3 }' >> delete

In the above you could grep for a regex and match a certain criteria. The output goes to the file "delete".

# cat delete |wc -l
168813

The list is even longer than expected because of some blank lines. That's why next we will delete all the blank lines with sed:
# sed -i '/^$/d' delete
# cat delete |wc -l
56271

And finally we delete them all, one by one:

#for i in `cat delete`; do exim -Mrm $i; done

The above may be impractical and too slow in some cases. If you need an immediate solution, you can simply delete the following directory:

/var/spool/exim/input/

After that restart Exim and there will be no messages in the queue :)))