Somehow Microsoft's own programmers do not seem to know the behaviors of their own webs server. IIS by default rejects requests with double escape sequence in the request URL. As a result, CRM 4.0 Email Router service may generate a lot of errors in the server's event log when it uses double escape sequences, saying that it was unable to access certain mail boxes on the Exchange 2007 server that it trys to connect to. Oddly enough, tests from the CRM Email Router Configuration Manager succeed every time. But errors in the event log keeps piling up.
The fix is to turn off the IIS rejection of double escape sequence.
Microsoft actually has a knowledge base article that tells us exactly how this is done: