Right now, the solutions being discussed sound much like the situation that has plagued email for the last couple decades: whitelists, blacklists, captchas, etc.
If there's anything we should learn from email it's that when the protocol isn't designed from the beginning to address abuse potential, you put yourself in a never-ending arms race against abusers.