So I did the migration of one of our clients from Exchange 2003 to Exchange 2010 and managed to get mailflow and everything working.
One issue that I have not been able to sort out is the Outlook 2010/2007 random authentication prompts.
When opening Outlook, it would sometimes prompt for your username and password (not always) and proceed to open your mail client and able to read your emails.
While working on Outlook, it would prompt for a username and password again, typing in the username and password would make the box disappear, but later return.
Note, this is not for ALL Outlook clients, it's random and no way I can replicate it by doing something. Exchange Proxy is unticked (users are stationary). Checked the connection status, attached are 2 files, 1 before password, 1 after.