Thank you all for the responses. It does indeed look like a parameter sniffing issue. My question was why did it keep popping up. Basically if the last name was Smith or Patel, the inefficient plan was actually better.

GilaMonster - regarding cardinality estimates, they are pretty accurate. Estimates are up to 6 when the actual number should be 1. As far as posting a plan, hard to do while also obscuring the data.

SQLGuru and ScottPletcher - as far as your ideas, the app team has pretty much refused to change the query. So, OPTION (RECOMPILE) or changing the PersonID<>0 are not options for me. Political issue, not a technical one. Also, I was leery of adding OPTION (RECOMPILE) for something that runs that often.

Ed Wagner - yup, typo by me....

So, it DOES look like I have a fix. We created a new index, that has the same elements as the [IXNC_Persons_LastName_PostCode] index, but with PostCode as the leading attribute. SQL was favoring PostCode anyway, now it can get all the info it needs from one index seek.

Looking at the stats, PostCode is almost as selective as LastName (within 2% looking at density). My theory, which I am looking to test, is that the similar selectivity combined with the much smaller data type influenced SQL to choose the original "bad" plan.