I tried the create statistics variant and that definitely improves the estimate, and with that one of the "bad" cases (the one with the 82 minute plan) now creates a good plan using only a few seconds.
That is a worthwhile path to follow. A bit hard to do, because those conditions can be anything, but I can probably calculate the ones used per customer and create those correlation statistics from that... It is definitely better than tweaking the "poor man's query hints" enable_xxxx 8-/ which is really not helping with plan stability either.
That will be a lot of work, but I'll let you know the results ;)
