Sounds like possibly the Outlook client is connecting with <i>RPC over HTTP</i> rather than a straight RPC connection, since the setting you mentioned is the default.
To check, look here:
If Outlook is open, from the File menu choose Exit.
Click Start and then Control Panel.
If Control Panel is in Category view, click the Switch to Classic View link on the left
and then double-click the Mail control panel.
If Control Panel is in Classic view, double-click the Mail control panel.
Click E-mail Accounts. The View or change existing e-mail accounts radio button should be selected. Click Next.
The Microsoft Exchange Server should be selected. Click Change.
Click the More Settings… button. Click the Connection tab.
In the Exchange over the Internet section (at the bottom), check that “Connect to my Exchange mailbox using HTTP is NOT checked.