Hi Dominic,
I've had a bit more time to think this through. I was originally hoping to use Audit Trail, but unfortunately there are no event types for tracking the deletion of a shortcut, only for the creation of a shortcut.
With that in mind, I think your best bet is to create a SQL table that holds the document entry ID/shortcut entry ID pairs. New pairs would be added when shortcuts are created, and it would be straightforward to do this for all existing shortcuts using the method discussed above.
I'm not sure what you want to do with the originating document's entry ID, but when a shortcut is deleted, the originating entry's ID could be returned from a lookup using the starting shortcut entry ID; then, it could be sent in an email, used for search syntax, etc. Alternatively, you could add a third column to the table to track whether the shortcut was deleted, and that way you'd have a record, if that's what you need (or you could just delete the row, etc.).
Anyway, just my 2c (again).
Best,
Rob