The "Silver bullet" for that problem was updating statistics.
As management calls it "Throwing virgin into a volcano with hopes that everything will go back to normal".
Finally that query reached my Management Studio.
It was extremely easy one and well programmed one. Precompiled, with passing parameters.
There were no visible problems other than linking five tables in a long chain, where results were extracted only from first and fifth and all filters were applied to intermediate ones.
There were some opportunities to create additional indexes, but knowing that query runs well enough without them stopped me with that suggestion.
So, I've advised to add OPTION (RECOMPILE) to a query to fix the problem.
Unfortunately, query is sent by third party application and it is close to impossible to change the app.
Then, if we can't do a query recompilation we can just force it to be recompiled by our "Silver bullet" - Update Statistics, but instead of invalidating query plan we can just simply delete that plan from SQL Sever cache.
Deletion of a single plan from a cache is usually manual task, but in our case we need something automated, when you just press the button to make a trick.
For that automation you have to know the signature of your query, because you want to target ONLY that query without any impact on anything else in cache. That query signature can be extended to multiple queries by using table name for it.
In my example I use following signature: "FROM Production.TransactionHistory".
All queries in in the plan cache, which happen to have that signature will be deleted.
Sample script runs against "AdventureWorks" database.