Don't think I'll be installing the toolbar anytime soon. Reminds me of the GMail controversy in terms of the privacy concerns. While I don't think either create enough problems to warrant not using them at all, I would be careful with both systems.
Update: check out danah's excellent "ickiness factor" and more privacy write-up. She articulates very well the issues around our discomfort with private information leaking out all over, and what designers might do to make things better.
One additional thought has to do with the "A9+everything you every bought at Amazon+everything is that there in your search history" information -- it's a preference threat, as it were, where your preferences are used to make decisions about you because someone can, because they gather your purchasing and browsing data, and decide you are X thing... and then redline you, or treat you differently or one-sidedly change what is happening without your knowing or consenting. It's a kind of threat that can have many manifestations, because the information leaks out to places the person did not intend when exchanging personal information for some purpose. When I get a driver's license, I think of this information, my driving record and the data on the license, as associated with driving, and some kind of state identification. When I purchase at Amazon, I think of that purchase as something between me and Amazon, not me+Amazon+all their partners+those that want to check out my interests beyond purchase (searches and intentions using A9).