Outlook Credential Prompt When Opening Exchange 2013 Public Folder

After completing an Exchange 2007 > 2013 migration recently, I was left with one issue that was preventing us from stamping the project as a roaring success and moving on:

Outlook 2013 users were sometimes receiving a single pop-up prompt for credentials whenever they opened the Public Folder (we have only one). One. Single. Prompt.

Google was frustratingly unhelpful because searching for "outlook prompts for username and password when opening public folders" or something similar just resulted in a lot of folks who were always getting a pop-up that wouldn't go away. It was usually caused by an authentication failure of some sort.

However, we were in a different boat - Users got the prompt once when they first launched Outlook and opened their public folders, but after entering it they could continue - authentication worked. Next time they logged in to their PC, it would happen again. Not a show stopper, but it definitely generated its share of support calls.