I totally agree. The complex queries I was talking about perform a lot of different actions, complex business logic is implemented in SP's. These kind of statements (seperate steps/parts of the SP) have inputs of which the domains are well defined. The individual parts of the resulting execution plan are stable. That is, until the described scenario happens. This will through everything of and a rethink of the rules, design etc is in place.

The fact that the inputs can mess up the execution plan, means that the domains of the input are not well defined.

If defining the domains is impossible, you are writing a system in which (parts of) the data is can not be defined upfront and you are probably better of rethinking the use of a relational database system (and a raise, because writing this is hell).

In a stable situation, the resulting plan should always be predictable and stable. If this was not the case, optimising would be useless.