Actually, although we are so used to it that it hardly matters, SSNs were never intended to be used as tracking numbers. You can refuse to provide it for billing purposes. Your phone company doesn't need it and neither does you gas or electric company. They can look you up by many other methods in a database, this just makes it convenient for them.

If they refuse, ask them why they are demanding it. They can ask for it, but you don't have to give it (especially if you have alternatives for their services). http://www.privacy.ca.gov/sheets/cis4english.htm
http://en.wikipedia.org/wiki/Social_security_number

The fewer people who have it, the better. Even financial institutions aren't always secure: http://money.cnn.com/2005/06/06/news/fortune500/security_citigroup/