At TechEd this year, Arpan Shah shared some MCMS search vendors:

• Coveo – Free for sites with less than 5000 pages. Coveo also has Enterprise Search for SharePoint.
• Snow Valley – Free open source search solution
• SharePoint Search

And some stuff I have come across:

• Mondosoft
• User controls for MCMS to use SharePoint Portal Server search
• IXIASOFT – XML-based search