Is there an easy way of removing all queued messages at once in a safe way?

Try this command:

exim -bp | awk '/^ *[0-9]+[mhd]/{print "exim -Mrm " $3}' | sh