I am having an issue where any mail sent to my server which includes an attachment, sits in the sendmail queue for a very long time, sometimes up to 20 - 30 minutes before it is delivered (or until i manually flush the queue).

Any mail that is sent without an attachment is instantly delivered and will be in the queue for no longer than a couple seconds.