Happens to me all the time. Basically, there doesn't seem to be PSAs for ad link units. When there's no ads to show on a normal ad unit, you get PSAs (public service ads). When there's no ad groups to show on an ad link unit, you get that search box.
You'll also see it on pages with a lot of stop words. You know, bad words. Here's a page where I get a daily variety of user comments that contain mostly the f-word. http://www.kbcafe.com/iBLOGthere4iM/?guid=20050609093511 You can see at the top, the ad link unit is a search box.