There needs to be a standard code in the NIP-11 doc that identifies the relay as a paid relay. That way you could just pull the NIP-11 and check it real quick.
Discussion
there's just one challenge that i was thinking about earlier: could it be in the interest of a relay to fake being paid?