Missing "Exchange over the Internet" on Outlook setup

We use a hosted Exchange for some of our e-mail accounts and I'm trying to set up Outlook for a new user. When I click the "More Settings" button in Exchange Server Settings, there is no security tab and no Exchange over the Internet section on the connections tab.

I've tried on 2 PCs. Both were XP Pro SP2. One has Office 2003 and the other has Office XP SP3. I have installed all Windows and Office updates on both.

I've set this up on dozens of PCs and laptops and have never run into this before. Our hosted Exchange provider doesn't know the answer. Can anyone help?