You’re welcome, Dima!
The best technique I know for encouraging users to enter natural language searches is to promote them through autocomplete. For example, on an ecommerce site, as people type in “jea”, you could suggest “jeans for men” or even “men’s jeans under $20” through autocomplete. Of course, you should offer suggestions that have some reasonable probability of matching the searcher’s intent. But hopefully, just by seeing such suggestions, searchers will learn that they can perform these kinds of natural-language queries and will be more inclined to do so proactively.
I don’t have any great examples to offer, but occasionally I do see natural language autocomplete suggestions on Facebook search, e.g. “friends who live in new york”. Of course, those are only helpful when they work, but they often do. Amazon showed me “jeans under 10 dollars for men” as an autocomplete suggestion — which would be great, except that the results themselves were awful. So if you’re going to encourage natural language queries, make sure you can handle them!