I already posted an evaluation of MondoSearch a couple of months ago (Check out CMS Search with Mondosoft), but lets add some remarks:
About SharePoint Portal Server Search
Some people argue that search isn't the best way to retrieve your document, it is better to organize you documents through the use of categories (SPS2001 terminology) or areas (SPS2003 terminology). I still consider search to be an essential part of SharePoint Portal. We have done some projects using SPS search and especially with customizations of the search or using SPS search to create or own rollup webparts, lets see what we have found:
About Coveo Enterprise Search
I downloaded Coveo Enterprise search last week after seeing the posting from Angus Logan, Coveo is an enterprise search engine and you are free to use it, if you index less then 5000 documents. It definitely is an ideal solution for small MS CMS deployments. I will write about it in one of my next postings.... I actually tried it out with an existing CMS site in a Windows 2003 setup within Virtual PC and it definitely is very easy to set up and very intuitive. I however experienced some timeouts when performing crawls, maybe related to trying it out in Virtual PC.