You know what, I'd assumed that they'd not been storing the data by individual phone number, but I'd not really thought about it. I just checked the EULA for GOOG 411:

"If you choose to connect to a business through the GOOG-411 service, your caller ID information will become visible to that business. We do not share your information with anyone except in the limited circumstances as outlined in our privacy policy.

To avoid having any information associated with your phone number in the future, just block your caller ID before you call...."

I guess I'm naive, sadly.