Use a service like this...
http://www.proveout.com/r/phone-verification.html
Tie account creation with phone verification. This eventually adds a cost to creating an account when you run out of numbers to use. Also a lot of these services allow you to block virtual numbers from service like Google talk, Skype, etc and payphones.