Yep, something like a bloom filter where the app could send a compressed list of events it already has would be great. Upload payload must be small, though.
Discussion
The trouble with bloom filters is it can easily become a DoS vector to the server. I suppose in the case of Nostr that risk could be mitigated with the payload being signed (where you aren't allowed to use bloom for read-only mode).