... can be just a fallback for when nothing else works (just delete my key).

The key insight here is that people become used to the practice of from time to time, scanning the network for some special events that signal that some keys may have changed, and then they stop following the old one and start following the next. This can be done inside their main social app or on a standalone app or website.