So I think, if someone used a paid relay and also connected to free relays, the users in free relays might still see the message eventually.

I think there should be a toggle in clients to switch events from free relays or paid. That should allow users to use both free and paid relays.