What about deleted nodes/ways/relations, but instead of giving an ID how about a bounding box so you can undo a delete?
For the moment I'm thinking about a changeset revert. In a changeset you'll get deleted objects marked as such. Finding a deleted node (or better: the changeset in which a node was deleted) in an area is another thing.
But one step after the another..
Peter