what about the option to pay instead of doing a POW? If you’re using someone else’s relay, I think they would prefer that.
I made a little project called pingkey https://pingkey.xyz/ it is a messaging app works like traditional mailing. You setup relays as your mailbox, people write letters and post them to you. Each letter must contain a POW which then turn into a unique POW stamp. It is that simple and I imagine it will become a alternative contact card for those people who are old enough that just hate social network and prefer to keep this simple way just like me. Feel free to try it and contact me https://www.pingkey.xyz/p/ce6232feaec4e6d01a4e00daa3648030c42017bdf589e34b53744fc49c5cba8a and give some feed back. 
Discussion
yeah I have such thoughts too. but there isn't a standard way (NIP) to allow relay charges per-message. Another more interesting thoughts to me is that we can have different stamps that is not comming from POW but human-made. So people can buy the stamp from other people.
I think nostr:npub1h0uj825jgcr9lzxyp37ehasuenq070707pj63je07n8mkcsg3u0qnsrwx8 is working on a whole protocol to make the stamp thing more common