Hi ,
If it is happening for all the users then we can check the outlook anywhere authentication but in your case it is happening only for some users and and they are splitted across different databases.
1.Please disable internet explorer proxy settings if you have it for the problematic user accounts and restart the outlook to check the results.
2.Then make sure outlook versions is having the up to date service packs which is required to use with exchange 2013.
3.What happens when you try to configure the problematic account on the different machines that is having other mailboxes configured which is working properly?
4.Did you exchange 2013 coexist with exchange 2010 or 2007 ?
5.Have you reconfigured the outlook profile on the same machine on where the issue is occuring ?
6.For checking purpose did you disable and enable the cached mode ?