You could dump the ids of deleted events in to a bloomfilter which is fast to check and small to store. 

At least in @nos.social when you view a post it makes a request to relays to get replies, labels, and reports. Adding a request to see if the author deleted it isnt hard. There would be a gap where the user might see then event only have the client need to update with a “the author of this post has deleted it.”

Or clients just rely in relays that a user is connected to being well behaved. We for example won’t post a note with an expiration timestamp to relays that don’t announce their support for the relevant nip.