Recently we performed some maintenance on our Exchange server at the office, we had to reinstall the Client Access Role in an attempt to regain OWA functionality.  After the maintenance was completed, we found that we were no longer receiving external emails, which was quite odd, as the only thing that had changed was the Client Access Role, which has nothing to do with External Mail.  After some investigation, I found that there was only a few hundred MB left on the C: drive, which is where the Queue database lives, and that with Exchange SP1, if there is 500MB or less available on the Queue volume, or with Exchange RTM, 4GB, the server will no longer queue mail.  It happened that when I was reinstalling the Client Access Role, the installers filled up most of the C: drive, causing the issue.  If you would like to read more about back pressure, and how to deal with it, I have posted some good links below.

http://www.petri.co.il/back-pressure-moving-queue-database-in-exchange-2007.htm

http://www.online-it-support.co.uk/?p=614