Search Box and Start Menu Problems

Sometimes when I press the Start button, the search box appears at the bottom of the Programs list as it should and other times it does not. Those times, the programs list appears, but it is a short list and does not end with the Search box at the bottom, but with one of the Programs. It is as if the Programs list is truncated before it reaches the Start box.

I can't find any pattern to this.

I have tried it with the task bar set to auto hide and not and with indexing on and then off (but not "search" ... "search" is always on.)