Opened a ticket with Microsoft, but as of this time have still not heard from anyone so we will be closing the ticket and asking for a refund.
We where able to restore the permissions with the help of a group on reddit.
Copied the Exchange install media to the Exchange server (C:\Temp\Exchange) and ran the following command at an elevated command prompt.
C:\temp\exchange\Setup.exe /PrepareAD /OrganizationName:"OurOrgName" /IAcceptExchangeServerLicenseTerms
This fixed the issue.