thats a little underhanded if you ask me
It (Google's policy) flops around a bit. It differs between countries and seems to get tweaked or turned over every so often. I believe in the US bidding restrictions on trademarked terms were recently removed. But you are still restricted in using trademarked terms in ads.
Personally, I agree that restrictions (bidding on trademarked terms) should be removed. I would compare it to handing out flyers on the street outside you competitions' shop. Tasteless maybe, but shouldn't be illegal. Companies don't own the search results, trademark or not any more then they own the street.
BTW, an interesting application of personalisation is not so much search ads (They are already pretty much the most targeted ads because search term is enough to target ads with) but content ads (eg adsense). Currently, ads are targeted using relevance to page content/site content or demographics of the users. But search history reveals a lot about interests & could be the key to 'fixing' context advertising (from the advertisers perspective).
I don't think this is worrying. If they start using personal data they hold, sure, but this is just creating a personalized experience. Lots of sites do it. If you don't like them doing it, disable cookies for them...
That being said, they haven't indexed my site yet. Amateurs!