Why would cached mode Outlook clients NDR messages for foreign connectors that Outlook online clients do not?

First, just a little background about address types and foreign connectors.
Address Types are ,as the name implies, the types of addresses that Exchange has knowledge of and that can be used for message transport.
There are several that are included with Exchange by default. You will see these stamped on each mail enabled user as proxyAddresses.
SMTP: (SMTP:mblanton@tailspintoys.com)
X400: (X400:c=US;a= ;p=TailspinToys;o=Exchange;s=Blanton;g=Michael;)
and EX: (Internal address type, not stamped on users)

You have always been able to add external address types to Exchange via gateway connectors. Fax connectors are a good example of this. Most of the time installing the a 3rd party connector will created the address type for you. Generally it will also create a gateway or connector mailbox on your server to handle those messages types. This is all based on EDK gateways which is outlined in the Exchange SDK.
 

Exchange 2007 will still let you install 3rd party connectors. These are now classified as foreign connectors.
These are installed with the "New-ForeignConnector" cmdlet.

Now on to the real question. When I install a new gateway or connector, why does Outlook work in online mode but not in cached mode?

In online mode when you send a message from Outlook, the message is submitted to the Outbox folder of your mailbox directly on the Exchange server. From there Exchange picks up the message and hands it over to transport for delivery.

With cached mode, Outlook tries to be a little smarter. Outlook will basically attempt to submit the message directly to transport queue for you. Outlook does this by requested and storing a list of available address types. If the address type you are attempting to send to is not on the list, Outlook will NDR the message before it ever attempts to connect to the Exchange server.
You can confirm which types are available by looking that registry keys for the cached mode profile:

  Name: 01026687
Type: REG_BINARY
Data:
00000000 03 00 0d 00 45 58 00 58 - 34 30 30 00 53 4d 54 50 ....EX.X400.SMTP 00000010 00

When the Information Store service starts, Exchange 2007 loads a list of address types which is stores in an array in memory. The key here is, when the Information Store starts...
When Outlook requests the list of available types, this array is what is returned.

Our problem comes about when a foreign connector is installed and the Information Store is not restarted. This array in memory has not been updated. Thus, as in my sample above, our Outlook cached mode client does not know about the FAX address type and Outlook will NDR any message addressed for FAX.

Simply restart the Information Store on the affected Mailbox server roles. This will update the array in memory. Then have each client log off and log back on to request the updated list from the Information Store.
You should now see the FAX address type stored for this profile and messages for address type FAX should work.

  Name: 01026687
Type: REG_BINARY
Data:
00000000 45 00 13 00 45 58 00 58 - 34 30 30 00 53 4d 54 50 ....EX.X400.SMTP.FAX 00000010 00