An update from today. Many of yesterday's invoices sitting in the EMail Queue have changed to COMPLETED over night. I still have an invoice from yesterday and one from today that are giving the must check for new mail first error, but there does appear to be some movement.

I have a theory that the mailbox could be close to it's maximum size, so I have requested the client look into this to see if that potentially is the issue.