As documented, the event delta API only yields the ID of the deleted resource, and no other attributes.
Our application uses iCalUId as the primary key to synchronize one instance of an event to an external data store. In our system, many users can enable this data sync, meaning events shared across multiple user's calendars will be processed, for which iCalUId uniquely identifies a single instance of a shared event, which is very important for our use case. This is not as simple as just replacing our usage of iCalUId with the internal id.
As such, when notified of an event being deleted, we cannot act on the internal ID alone. Ideally, these notifications would come with other information about the event resource that was deleted, such as iCalUId.
Is it possible to retrieve this information with the current version of the graph API? Or is there a different approach entirely to this sync strategy that makes more sense to pursue?
The service doesn't support sending more information than just the MS Graph id on deleted events today.
A workaround would be for you to sync the MS Graph id & the iCalUID on previous events (addition, updates...) and then to remove events from your storage by mapping with the MS Graph Id.
You can also request for additional properties to be added to the deleted entries on Microsoft Graph Uservoice.