In the User's properties, click on the Exchange Server and then properties again. Click on the Advanced tab and change the "Logon network security" to none. This will prompt the user to enter username/password each time he/she tries to open thier account.
I have asked this same question a few times before I implemented Exchange Server 2000 and Outlook 2000. Took a while before I was able to find a solution.
Like pjm said, make sure you say "prompt for a profile to be used".
Let me know if you have some troubles...I can send you some screen shots.
Nick