На курсах узнал фичу, что Microsoft Outlook 2007 не будет работать, если в свойствах TCP/IP не настроен шлюз по-умолчанию.
Погуглив узнал, что уже и kb913843 есть с решением в виде правки реестра вместо настройки шлюза.

От оно как бывает … Интересно, как оно в Outlook 2010?