Yes, the Search link on Start menu has been removed.
Brandon Leblanc over at the Windows Vista Experience Blog explains why:
"Microsoft has recently published a KB article outlining changes to Windows
Vista's desktop search in SP1 but I'd like to elaborate a little bit based
on my own experience with the changes. Windows Vista SP1 allows the user to
change their default desktop search provider from the built-in Windows
Desktop Search that ships with Windows Vista to another 3rd party desktop
search provider. As noted above, the Search option has been removed from the
right side of the Start menu. Users will also notice "See all results" has
disappeared when doing a search via the Start menu. Instead, you will see
"Search Everywhere". Search Everywhere will launch whatever is the user's
default desktop search program. In Windows Explorer, users will also see a
"Search Everywhere" option in the toolbar as well."
My Vista Quickstart Guide:
"bassam" <email@example.com> wrote in message
> yes iam running Windows Vista SP1
> so now i can't display the search in my start menu ?
> "Andre Da Costa[ActiveWin]" wrote:
>> If you are running Windows Vista SP1 beta, the Search link on the Start
>> has been removed. If you are not, then it has somehow been unchecked,
>> click Taskbar > click Properties > Start Menu (tab) > Customize > scroll
>> down and make sure the 'Search' option is checked.
>> Also note that the Search field is not available if you have the Windows
>> Classic Start menu enabled.
>> Blog: http://adacosta.spaces.live.com
>> My Vista Quickstart Guide:
>> "bassam" <firstname.lastname@example.org> wrote in message
>> > Can't find Search in Start Menu .... even in customize under start menu