I suppose that next question is how do I handle this?

Assuming I can get the front end code changed(unsure about this though):

1. Simplify the query if possible?

2. Add RECOMPILE option in the query ??

If I can't get access to the front end code:

1. Run another update stats during the day?

2. Turn on adhoc for workloads so more plans stay in the plan cache longer??

3. Add a plan guide for this query so it RECOMPILES?

I don't really know what else would help

Sorry, I will have a read of your links in case you have the answers already listed.