It's been a while since you posted this question but eventually it helps someone other who gets here..
I'll just explain what worked in our environment:
1) Make sure you have installed Outlook 2010 SP2 or Outlook 2013
2) When adding your Outlook Account you need to do/check following:
-Leave Exchange-Caching Mode Enabled (You can disable it later)
-Before clicking "Finish" go to "Advanced Settings" and under "Security" check if you have enabled to encrypt data betweend Outlook and Exchange (Checkbox), do not tick to ask everytime and change Network Security at Logon to NTLM authentication. The NTLM setting also applies to Exchange Anywhere, but this should be default there. If you forget this part, you can't change it afterwards, it always discards your changes after you apply them.
3) When starting Outlook you may have to enter account settings for the first time. (Don't forget ticking "Save Credentials")
4) Same goes for every additional Account you add to your Outlook.
Short Explanation: If you have more than one Account in your Outlook, Windows somehow is not able to tell which Account needs whose authentication. By enabling Caching-Mode and changing Settings to NTLM it should add an Entry in your Credential Manager for each additional account you add to your Outlook. (If you are using a proxy server you may have to disable this one if the stepas above didn't work) If this works correctly, it should not ask for your password again each time you start outlook.
If the entry has been succefully made, you need to remove the login information for your webmail (Otherwise you will be having trouble configuring your Out-of-office messages)
Sorry if some of the setting-names do not exactly match the correct ones, i'm using outlook in another language.
Hope this helps someone out there.