An issue I came across that had been caused by the migration of Public Folders from Exchange 2007 to Exchange 2010 which is resolved here:

http://blog.samkendall.net/2010/09/07/exchange-2007-to-2010-migration-public-folder-issue-fix/

In essence any mail enabled folder that came across was failing to receive e-mail with the error:

This is resolved by remove the empty Servers container in ADSIEDIT under the old Exchange Organisation