Re centralization: If you choose to pay relay A and not relay B, then why would relay B accept your posts? I am assuming they would not; otherwise, relay A can easily spam relay B (if relays compete for payments, then they have an incentive to take down competition, and spam is a way to achieve that).
Discussion
Hmm, an interesting perspective. First, to be clear, most of these proposals are "self-verifying" so to speak, so the question doesn't arise (i.e. proof of burn, proof of work and aut-ct). Specifically for a payment though, like ecash, I imagined it as "user has N entry point relays, relays talk to each other" and the latter is a matter of relationship between relays. I suspect that's how it works today. Relay X just blocks relay Y when it sees it sending a bunch of objectionable spam, otherwise they choose to cooperate. As for relays behaving adversarially because they might be in economic competition, that could be a good point, I'm not sure.