To be honest, it really depends on how ambitious your ideas are. The biggest cost is in acquiring the horse-power to actually make a competitive engine. There are hundreds of off-the-shelf commercial friendly engine backends that can be used to power the beast.

Things to consider: (a) Are there products already out there like what you're thinking up? (b.1) Are there backends available that will allow you to add your changes seamlessly without too much hassle? (b.2) If no, will you need to roll-your-own? If yes, do you have the skill-sets and man-power that are necessary to get it folded in? (c) What kind of domain are you after? World-wide-web, news articles, medical transcriptionist records, the files on someone's computer, etc.? The bigger the domain the more money it's going to take. (d) Aside from the financial costs, how much time-money would this endeavour cost you and how much turn around can you expect to see from it?

These questions really need to be answered before you can decide how much a "search company" is going to cost. There are lots of search companies with a variety of target markets and a variety of needs. Sadly it isn't a very satisfying answer, but I hope it helps you. :D