We had noticed that the machine account for one of our exchange servers had been deleted. Due to this exchange had stopped working and could not be logged into using a domain account, after quite a bit of research we came to the conclusion that it was safe to pull exchange out of the domain and then re-join the machine back to the domain.
This fixed the problem with the missing machine account but exchange didn’t come back up and report some errors, which meant permission problems.
We checked the permissions of one of our other exchange servers, and add the machine account for the problem server to the same groups. As soon as the server picked up the new permission exchange start functioning again, we rebooted the server for it to pick up the new permissions.