Can a way's ID appear again after the way is deleted?

I've seen POI nodes relocated when, for instance, a restaurant moves -- sometimes a mapper will simply drag the node from the old location to the new location, keeping all the same tags (other than address, hopefully, if the original node had address tags.) And one could imagine a deletion in between, ie, one mapper notices a restaurant is closd and deletes its node, and another mapper reverts the deletion then moves the node to the new location.

This same process could happen to a restaurant mapped as way -- as a building, for instance. It could be deleted, the deletion could be reverted, and the way could be moved to another location. Sometimes buildings do move (generally not all the way across the globe of course) and if so this might actually be the preferred way to map that. A mapper might also choose to do this so that the https://www.openstreetmap.org/way/ID# link to the previous location would still work for the new location.

I don't know of any examples.

But in short: Yes, any deleted way can be reused by reverting the deletion, and might also change location. This probably won't happen, though, unless a mapper is doing it intentionally. It won't happen "naturally" when a new way is created.

[Edit - it's important to remember that ways don't actually have a location, only nodes do. Ways simply have an ordered list of nodes. So if nodes can move across the globe, you should assume that ways can too.]