Background: About a month ago, we ran into a peculiar situation where store.exe on one of our mailbox servers was repeatedly crashing, with Event ID 9673 being generated in the Application Event Log from MSExchangeIS.  Per KnowledgeBase article 959135, the appropriate fix for this was to apply the recently-released Rollup 7 for Exchange 2007 SP1.  That didn’t fix the issue, but instead the crash rate increased.  After a marathon consultation with Microsoft Premier Support, we discovered that, in addition to the installation of the rollup, it was necessary to create a registry key called “Search Folder Nesting Level” in HKLM\System\CCS\Services\MSExchangeIS\ParamtersSystem and set it to a value of 10 (down from its default value of 20). At the time of the incident, the need for this registry setting was not yet mentioned in the KB article.

The following Monday, we received a report that messages to one of our users was bouncing with a rather enigmatic NDR notificiation

:#550 5.3.4 STOREDRV.Deliver: message exceeds fixed system limits. The following information should help identify the cause: “MapiExceptionTooComplex:16.18969:890F0000, ….

Go ahead and Google “MapiExceptionTooComplex” – I dare ya.  You won’t find anything useful.

Moving the mailbox in question seemed to resolve the issue, and we thought we were done with it.

This last weekend, I finished applying the rollup (along with creating the registry setting) on our remaining mailbox server nodes, but today we began receiving reports of the same bounce issue, including issues with the same mailbox with which we had dealt previously.  Consulting once again with Microsoft Support, it was recommended that we set the aforementioned registry key to 500.  This ended the bounces, but now we find ourselves in a catch-22: keep the mail from bouncing to select mailboxes, or risk a repeat of the store.exe crashes.