I have a solution with a Azure table storage with up to a few tusands "rows" per customer (partition key).
How do I best do a lightning fast free text search?
Because of the nature of the data I'm not able to do a hole word search (eg. a search for "zur" should match "Azure").
At the moment there is no out of the box solution for this. Perhaps a full text search feature will be announced at PDC10.
So at the moment you will need to roll your own text indexing solution. The way I have done this is by building a Lucene.net index on a worker role. I then open a tcp port on that worker role that provides a search service using WCF. Any web role can then consume that service. This works really well and provides a very fast search service.
There is a PDC09 video by Steve Marx that gives more information: http://www.microsoftpdc.com/2009/SVC16