What is your size set it to on your mail servers? Exchange has a place for limits as well. Are you sure it wasn't a message from GMAIL? I don't think they allow a message size like that.
On the Exchange server the size was set to 40MB for those mailboxes. The Gmail mailbox allows 30 MB.