Wrong!
If I had checked this link here I would have seen that Office 2007 requires Service Pack 3, which I had not applied to my workstation. Since Outlook was only Service Pack 2 I could not connect to Exchange, received the constant prompts for authentication and the eventual ‘Offline’ showing in the bottom right hand corner. Prior to looking for this fix, I checked Event Logs on the server and Exchange Server 2013’s logging directory for clues. Eventually I decided to run Windows updates as well as Office Updates. That’s when I noticed that I did not have the latest updates on my Office applications – Service Pack 3 was not installed. I then did a quick search and found the article from TechNet that shows the following versions of Outlook are compatible with Exchange Server 2013:

Although we all joke about making sure you have the latest service pack before calling support, in this case it was the correct fix for the problem.