It's funny, at my company we implemented deduplication almost exactly the same way for our push notification sender.
The scale is smaller (about 10k rpm), but the basic idea is the same (store a message ID in a key-value store after each successful send).
I like the idea of invalidating records by overall size, we hadn't thought of that. We just use a fixed 24-hour TTL.