We have been encountering an issue where upon random Outlook 2013 users are unable to open the address book, or add a room to a meeting (using 'Add Rooms...' button), and an error message is displayed that the server is unavailable. Mail flow and everything else functions normally.

If I look at the Outlook connection status of an affected user, I will see that all connections are established except for the 'Exchange Directory' connections which show disconnected. If I click the 'Reconnect' button the Exchange Directory connections are re-established, and the user can now access the address book/meeting rooms as normal.

Are there any ideas what I would check, logs I could look at, events or anything I can check on the server side that might lead me to an answer what could cause this?

Outlook 2013 gets that data from Exchange 2013 by connecting to Exchange Web Services.  That's where you should look.