An alternative to PoW is just to pay the relay a fee directly to accept their event. The downside here is that when you pay a relay, you then need to pay the next relay, and the next relay.. where as if the relays accept either payment or a minimum PoW, then you can generate PoW once and broadcast to all relays - which is more censorship resistant as well.

A relay that I believe does what you’re after is strfry. It should cover your needs today.