Looks like they have made it a permanent change to the ads. Maybe doing this to try and boost clicks. Before you would see them every once in a while, now just about every ad has them.
While many of you said that they have been around for quite a few months it looks like google has just recently "officially" released this new ad format: http://adsense.blogspot.com/2008/04/show-me-ads.html I'm seeing them everywhere now!
Anyone have any stats to show increased eCPM since the change was implemented? For me, if there has been an increase it has been very small!