Captcha technology will not work with phone services because...

1: It requires too much work on the human end

2: Captcha-beating software can/will be easily created by the robo-calling companies. Think about how deathbycaptcha.com works (computer + human decaptcha service), and even how ASIRRA by microsoft research was defeated in about a month simply by making a database of the possible questions.

What I propose: The robo-calling messages are pre-recorded. There should be a few steps... Step #1: See if a phone number is making more than 6 calls in a 30 minute period. Step #2: That number is now suspicious, scan the waveform of the calls made in that time to see if there are exact similarities durring the conversation (may do windows of 5 seconds, because they may inject a dog bark at the end to throw the scan). Step #3: If it is shown that the calls are rapid, and share clips that are the exact same (which wouldn't happen with a human voice), that number is now blacklisted from making more calls for a month.

The reason this will work is because in order to fill orders of 20k phone calls, the company would need to burn 2000 phone numbers (assuming 10 calls get placed before number is investigated and banned). The costs would be too high to sustain the business.

Another possibility is when a number is found to be sending robo-calls, all of the numbers with the same prefix (first three digits not including area-code) could also all be scanned automatically. This would help because I assume these companies buy numbers in bulk.