I have made a good experience with Amazon EC2. You have root access as with a "normal" engine and you can install whatever you need. You could start with a small server and easily scale out.
I made it similar and started with a cheap micro sized instance. Here is how i upgraded:
As you can see, its straightforward.
For testing, AWS offers a free tier for 1 year. You could try it out pretty well and then decide to stay or leave.
The good thing with AWS is you can easily buy extra services which are managed. For example, if DB management gets to complicated because of too much data, you could buy an RDBMS instance from amazon. They do care on the gory OS details themselves. For the start it might be enough to install your own Database on the EC2 instance.
Also they provide Loadbalancers etc.
Another option would be to use PaaS (platform as a service). Like Jelastic:
- Openshift.Redhat.com (beta)
and so on. The problem is they limit your access. Most often the provide a container like Glassfish, but you usually don't have root access.
If I were you I would check out if there is a Lucene provider who offers Lucene as a service. if that is not possible I would go with EC2. It seems you have some special needs and it might be required to build up something on your own. AWS is giving you most freedom you need, altough you need to work as $root and therefore read the docs.
As a last note, I have learned from experience that "using the first option and migrating later" is a bad idea. Once you have chosen your host, you'll stick there long time. It just to painful, riskful and complex to "simply" migrate. Better take a few days more on thinking about that matter than chosing a quick/dirty solution.