did you try changing the compatibility level to check for cardinality issues?

We have had many and some times the quick way to tell for sure is to switch it, then test.