I'd ask for their cell number and send a verification code. That'll stop 95% of all duplicate accounts. Keep the hash of their phone number in a hash list, rather than the number itself. Don't allow signups from outside whatever region you can SMS for free.
I realize this would mean relying on an external protocol (SMS), but it might just keep the crap out. Would help for ban evasion too, at least within an instance.