Yea, we have the right license.
To solve this we had to log into the web interface (OWA) for the user and checkmark the personal retention polices that were assigned to the user through Exchange admin. Then restart the Outlook client. After that, the policy button appeared in the Ribbon under Folder and the user could assign the policy they want.
That seems like a step that shouldn't be necessary but it worked.