Can we accomplish this without any per-peer storage? Probably something like “the last time I was online, running, and received gossip was block header/timestamp X”. From there any peer that does receive-time tracking should be able to go back into their gossip history and check for everything newer than said time (minus a fudge factor).
Of course that assumes nodes keep track of when they received all gossip messages. Currently we only track that for channel announcements, not updates. TBH I’d really rather we Just Do Minisketch and move on rather than trying to keep applying bandaids to the current gossip.