Users can always revoke their public keys. The same public key does not have to be used continually. Allow users to revoke their keys as often as they like. Heck, force the keys to expire in 1 day if you like! We already expect the sender to be online. The sender can check for key revocation before they send the message. Or let the server send back a error response if the sender used an expired or revoked key to encrypt the message.