We have migrated to Exchange 2013, everything except the Public Folders have been moved.  We are having an issue with Outlook 2007 clients connecting.  They have been updated to the compatible version.  The outlook-anywhere internal and external authentication methods are all NTLM, IIS authentication is Basic, NTLM, negotiate.  

We've tried removing/re-adding profiles with no success.  

Outlook 2010/2013 work fine.  What the flip am i missing?  

 

Give a look at the connection monitor and see if it is the public folders. I just moved an organization from Ex2007 to Ex2013 and had that same issue and turned out that it was the public folders which were still on 2007 causing the issues for the users on 2013. Neither I nor Microsoft could figure out why exactly the PFs were causing the authentication to prompt, but it was clear that was the cause.