Solr or Sphinx based searching is what pushed me out of most of the PaaS offerings and into my own VPS. It's unfortunate that most of the hosted services out there are too expensive for side projects.
When I looked at WebSolr, the cost exceeded my entire VPS structure, even for their cheapest plans.