We have spent some time comparing MOSS search and WSS search in our lab. For those who are interested in the differences between MOSS search and WSS search, this blog post might clear things up.
WSS 3.0 Search
Single Site collection, automatically scoped to current site (and subsites):
Only SharePoint content in the site collection can be crawled. You cannot configure Search to crawl databases, mail servers, application servers, or Web sites and file shares outside of the site collection. In a deployment with more than one site collection, each site collection provides Search only for content on that site collection, and there is no aggregation of search results across site collections.
MOSS uses an enhanced relevance algorithm for its search engine, and is able to crawl content from multiple sites within an enterprise, as well as non-sharepoint web sites. In short, the MOSS search engine is a powerful enterprise search engine with a relevance algorithm, while the WSS site-local search engine is actually pretty useless beyond simple "dumb keyword" search.
Site Directory MOSS provides a new site template called "Site Directory". When you create your first portal via MOSS, it comes with a Site Directory. This site template is designed specifically for tracking links to sites, displaying site maps and site navigation lists, as well as searching through the site directory. With a Site Directory in your portal, you will be asked if you want to publish a link to your new site every time you create a new site within the portal, regardless of its depth within the hierarchy. This single feature is, in my opinion, absolutely required for any kind of Intranet deployment of SharePoint. And yes, that means I think MOSS is a requirement for any real Intranet deployment of SharePoint on any kind of meaningful scale.