I intentionally was vague because there are many possible existing ways to accomplish each thing I said, and it is up to the phone company to innovate.

The simplest way to keep people from guessing phone numbers is to make them very long and sparse. If an autodialer had to dial 1000 invalid numbers before finding a valid number, it would make the endeavor that much harder. This is just a convenient example because the cryptography equivalent is harder to explain, but you could make contact info so hard to guess that it would be basically impossible.

Probably the easiest way to explain how to keep people from passing contact info is to imagine a two step process like facebook has. If I pass your facebook username to someone else, they don't automatically become your friend. The cryptographic equivalent would involve a chain of trust, but again, harder to explain.