Maybe get someone who knows about the product
Since Exchange 2000, it's been tightly integrated with AD. In fact, it was one of the primary drivers for the invention of AD. You don't have to maintain a separate x500 directory any more - it's baked in.
These idiots should not have been anywhere near Exchange if they did not understand the close connection between AD and Exchange user objects. A mailbox is simply a database object - nearly everything to do with it is configured as a user property in AD. Whether that mailbox is located on-prem or Exchange Online. So yes, deleting the user object from Exchange DELETES THE USER OBJECT in AD, assuming you're using the default OOB permissions model. Which, guess what, were developed in the late 90s to allow admins to manage mailboxes and users seamlessly from the same directory (since user admins almost by default became the Exchange admins - you put in AD to have Exchange!)
Now, there is such a thing as a split-permissions model that can be done in two basic flavours. 1. complete separation of AD admin from Exchange - you cannot alter AD user objects from the Exchange console. Rare, especially early on, when of course your Exchange and AD admins were the same people. There's also what MSFT calls the "RBAC" model, where certain objects can be managed by the Exchange console to varying degrees. Such as the ability to update distribution group memberships but not delete user objects.
It's quite flexible and granular and the product is actually pretty capable in that respect. IF YOU KNOW HOW IT WORKS.
The fact that these numpties didn't even know that the accounts synched to Azure AD (and the mailboxes in Exchange Online) are linked to the AD accounts is jaw-droppingly stupid.
Also, by the way, if you have an on-premises AD, you MUST HAVE ONE EXCHANGE SERVER IN HYBRID MODE ON PREM. I had this argument with MSFT a few months back, since we sync the accounts with AAD Connect (which purportedly syncs back user and group email attributes to on-prem AD), but there are some magical incantations you still need an Exchange server for, even if it's a tiny VM (and has no mailboxes or SMTP traffic). I'm not going to summarise why here, but just be aware.
Finally, the thing about the "Linux backup" being able to restore the AD accounts is a frigging ridiculous point. It doesn't matter what OS the backup runs on if it's AD-aware. Yes, AD is a customised LDAP database, and if the product can read the objects, schema and perms with its action account, big whoop-de-do. It worked as it should. Whether running on VMS, Linux, Solaris or a non-domain-joined Windows server.