What version of exchange are you running? We had a similar issue here last week (on ex2010) with a receive connector not allowed to process anonymous mail. So Mimecast couldn't get anything to us and created a load of bounce backs.
That doesn't explain internal mail though - can you try restarting the SMTP/Transport services?
Do you use any sort of 3rd party spam tools? Every so often our GFI mail essentials garbles itself and stops email flow leaving us to have to restart the services for it.
EDITED: 30 Jul 2013 11:34 by GRAPHITONE