Why is SQL exeuction plan so different, and query so slow, after db restore to another server?
This post has DB1 and DB2 query plans.
More importantly, both execution plans are on fairly rocky foundations, DB1's just happens to be better in practice. Look at the difference between the estimated and actual row counts – there are very significant differences in multiple important places.
It's always possible that improving indexes might result in an improvement in plan stability, but there is a more fundamental issue here: larger sequences of operations (joins, aggregates, filters) always reduce the quality of statistical information. There comes a point where the estimate from statistics just cannot be made reasonable.
At that point, a sound strategy is to break the query up into two or more parts, using a temporary table to store a small intermediate result set. The optimizer can create new statistics on the temporary table, and there might be an opportunity to index it as well.
Smaller plans with more obvious access methods (indexes) almost always produce higher quality and more stable execution plans.