Yes, the Search link on Start menu has been removed.
Brandon Leblanc over at the Windows Vista Experience Blog explains why:
Quote:
"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."
http://support.microsoft.com/?kbid=941946