It should not matter if businesses store your SSN. Would you object to storing your name, email address, phone number, postal address or any other publicly available number or information? The SSN should not be any different.
I'm afraid that the real problem is that businesses (and possibly government officials) are using SSN as authentication token instead of identification token.
We have exactly the same problem here in Finland with our SOTU/HETU/what-ever-it's-called-today identifier string. It was originally designed to be identifier for every citizen but the latest law (Henkilötietolaki, 1999) says that this identifier should not be public... Or it can still be used for identifying persons for statistical reasons, for selling services for credit, renting, insurances and other miscellaneus stuff. However, it cannot be used as the person idenfier "only because it were the easiest way to identify a person" (direct translation from the actual law)! How fucked up is that? A personal identification number that shall not be used as personal identification number? To my knowledge this originates from using this identifier for authentication (surely you are the only person that can remember the last 4 symbols in your identification number?)... After reading this discussion, it seems clear that the problem is the same in the USA. What I cannot understand is why they decided to codify this brain-damage as a law instead of simply saying that you cannot authenticate with identifier.
How can we get businesses and government to regognize the difference between identification and authentication? SSN or any other non-secret is not an authentication token and MUST NOT require any protection to keep it from public. One simple method would be to pass a new law that practically says that "SSN number cannot be used as an authentication". As a result, anybody using the SSN for authentication would have no authentication at all, according to law. Hopefully that would be clear enough even for dumber businesses.