I've seen that on 2006 Juny and July, just at bottom of 300x250 ads (below three real ads). But I've never seen again.
Yep, if they can't figure out what your site is or the inventory is empty (both of which now are unlikely), then it pops that up in place of the text links.
actually, its related to the table used in scripting. if you choose 5 links and your table has lower width, this appears. works like a search box.