Recovery of Exchange Contacts

Do you still have access to the Exchange account? If so, re-add it to your phone. If not, then they are gone and there is nothing you can do to get them back. The contacts synced with an Exchange server are "owned" by the server.

You can’t recover them. They were always in an Exchange contact group, and when you deleted Exchange that group disappeared. If you wanted to keep them you should have moved them to a different contact group using an app like Groups.

"Outlook" may refer to:

Microsoft Outlook, the standalone mail client for PCs, Macs, and mobile devices.

Outlook.com, the online email and cloud services provided by Microsoft.

Microsoft Outlook is the client software most often used on PCs and Macs to access Microsoft Exchange services. People often say "Outlook" when they mean "Exchange".

Please clarify what, exactly is missing and where it was before.

The issue seems to be that the Contacts are not being sent back to Exchange but only stored on the device and iCloud but tied to a group associated with that particular Exchange Account id. We are migrating our users and all the contacts are being migrated as well but they aren't showing up after reconnecting the Exchange Account. They are just missing. Pretty frustrating user experience.

That is probably done intentionally to prevent intermixing company contacts with other contacts on the phone.