I laughed, then had another idea: Rather than send the server one number to check, generate another 99 random numbers in the client and send them all to the server. The client receives the status of all of them and shows the status of the entered number. The server never knows the actual number, and the phone number address space is saturated enough that many or most of the random numbers are also real numbers.
