Você parece estar confuso com as ofertas de versões diferentes (não é surpreendente).
A licença do MOSS Standard inclui a funcionalidade do site de publicação do CMS e toda a funcionalidade do Search Server, que pode indexar todo o conteúdo do SharePoint, além dos sistemas de arquivos e de outras fontes. Não há necessidade de comprar outro produto.
Sim, todos os usuários que acessam o servidor precisam de uma CAL. Eu não sou um especialista em licenciamento, então não sei se uma CAL do Office é suficiente, eu acho que você precisa de uma CAL do SharePoint. Ligue para o representante local da Microsoft e peça para ter certeza.
A funcionalidade de pesquisa na CAL padrão pode, definitivamente, retornar resultados de vários conjuntos de sites. Consulte Qual tecnologia do SharePoint é a certa para você? e Download de comparação de produtos do Microsoft Office SharePoint Server 2007 (que está um pouco desatualizado) para obter mais detalhes.
Mais informações
Quando o SharePoint 2007 foi lançado, havia o SharePoint Server para pesquisa, o SharePoint Standard e o SharePoint Enterprise. No ano passado, a atualização de infraestrutura para o SharePoint foi lançada. Isso adicionou vários recursos, como pesquisa federada ao SharePoint Standard e Enterprise.
Também nessa época, o SharePoint Server para Pesquisa foi renomeado para Search Server 2008 e um novo produto, o Search Server Express 2008, foi lançado. Ambos os produtos do Servidor de Pesquisa são direcionados a empresas que não desejam implantar o SharePoint (ainda).
Se você implantar o SharePoint, tenha certeza de que, desde que a atualização da infraestrutura e / ou o Service Pack 2 estejam instalados, você terá todas as funcionalidades do Search Server e muito mais. O Search Server é um subconjunto da funcionalidade do SharePoint Server Standard.
Como um aparte, você pode encontrar este livro útil em mostrar o que pode ser feito com a pesquisa.