Outlook keeps prompting me with a "Message too large" error every few minutes. I had tried to send an email with a 34 MB attachment, not knowing that there's a size limit for outgoing email messages. After searching long and hard for a solution, it ended up being very simple to fix and did not require me to delete my mail account and start over (which was the typical advice I saw from google search results).
I'm using Outlook on a Mac, with GMail as the mail server, which is a fairly typical setup. Here are the messages I was receiving. There were also no messages in the Outbox or Sent Items folders.
Open Outlook and find the Trash folder. You should see your message. Just delete it and Outlook will stop prompting you with the error message.
That solved the problem for me.