I had to reinstall W7 yesterday and after some initial setup shenanigans, I found that the best feature of Windows 7 - the Start Menu program search field - was missing. These things are usually sorted via the Customize option which can be reached by right-clicking the Start Menu. However, I could find no option for the search field. After much hemming and hawing around, I decided to retrace my steps during the initial setup that I did and wonder upon wonder, organised strategies do work!
The search field is a feature of Windows Search (which makes sense). I'd turned this (and many other seemingly redundant add-ons) off via the Programs and Features control panel snapshot. These options are sequestered within the Turn Windows features on or off link which resides at the top-left section of the snapshot. Turning Windows Search back on and a reboot (typical :S) later, my Start Menu search field was back!
Hope this helps somebody out there!