Problem: Linux Server is choking on its mail and you're a near total Linux newbie.
A) Flush the queue.
B) Go into the mail queue (in my situation it was /var/mqueue/) and move files to another location. using mv * ../030204
You may want to count how many files are there at the moment:
ls -l | grep -v ^l | wc -l
If you are hemmed in by a queue full of legit and dud messages, you may have to move some of the files. However, that might give an Argument List Too Long warning. To remedy that, move some of the files.
mv qf*01 ../030204
until you have the right messages out of your queue. Make sure you're off loading old messages. All messages climb in an alphanumeric order. For example qfj4I----- is and older piece than qfj4K----- and not by two days neccessarily. Sendmail will add letters to its queue messages as it needs them. A hour or a week may separate a naming change.
C) read the X FIles. (ls x* -al). These will point you to the possible cause of the failure. In my example, the /var/spool/mail/marc file had filled to capacity. I nuked it and went in search of the root cause as to why it wasn't tidying itself up.