I agree with the direction Tom Sparks answer goes. But I don't think you have to move out of the VM to build availability + security.
In any case it obviously depends on the specific problem you are solving and how you are solving it. Even saying 'Building a Search Engine' is too broad. Installing something like Solr and ElasticSearch or writing search software? What type of information, what type of queries, performance, amount of data, cost etc. All of these things obviously drive your architecture and one only truely understands the details when you actually start solving the problem.
So I would say if you haven't got that far start with any of AWS, Rackspace, Azure etc. that provides enough of the basic infrastructure building blocks, build the initial parts of the system (prototype).
You probably have enough info then to make the next choice. Just make sure you don't lock yourself in too early to any provider specific technology.
Original thread on Quora