I have a multiuser license and am able to map to the exchange folder and connect a database to it for initial sync. However, when going to “Store All” records, the prompt comes up suggesting I do not have a database linked. Thing is, I do have a database linked. Am I missing something here? Can send a screen shot if helpful.

You must select the folder in Outlook and than hit manual sync. button (Load item, Load all, Store item, Store all).

If the folder is not visible in current view, switch in Outlook to Folder List View and select the folder.