Further to our last post of two days ago, a little research digs up the fact that Symantec/MessageLabs “had a major incident … that led to an issue with multiple customers.” As we suspected, the problem was not with our mail server.
The message backlog was actually finally cleared within a couple of hours of that post.