Put pressure on relays to adapt a requirement of paying a small fee to use the relay.
Look into using paid relays over free relays and boycott free relays.
I completely stopped spam by requiring a fee of 0.10 cents USD on my forum. I could even go much lower.
It's the only way to stop spammers.