After rebooting a server we found the following error in the event logs along with whole stack of others:

Right, so the Microsoft Exchange RPC Client Access would not start. To fix this error, you can do the following:

Locate the Remote Procedure call (RPC) Locator service and set it to automatic and then start it:

Now scroll up to the Exchange services and stop the Active Directory one which in turn will stop all of them.

Now start all the Exchange Services and you will see that the RPC Client Access Service now starts:

Hope it helps.