I noticed when doing a search, that at the top of the 'search suggestions', box, a clickable adwords ad appeared. (for the company whose name I was typing). This might not be new, but I never saw this before...
I only saw this when using the google.com/ home page for the first time.
I'm going to make a very rare exception here about allowing self-linking. If I'd dug into my memory banks a bit more thoroughly I would have remembered that article from over a year back and linked to it myself - it's very helpful to this topic and a clarifying answer.
So Adwords in Search Suggestions have indeed been around since Dec 2008 - I guess I just don't visit the right search neighborhoods, because I really haven't been noticing them.