It's technically possible by caching only deleted shapes if any operations in the undo stack are associated with them. But is it really the UX we want every time it's happening?

Let's imagine that we work together on a design file that contains hundreds of icons. I'm responsible for adjusting the color palette while you're removing the old icons that are not used anymore. If I undo my last color update on all icons, I probably don't want to recreate the icon inadvertently and override the triage you're doing! So IMO, it's more of UX question than a technical question. Is there a better default solution that we can find to improve these edge cases? My initial thought is to have a small "toast" letting the user know that the undo operation couldn't be applied because X does not exist anymore, with a link to the version history panel to allow him to reinsert X if it wants to.