Slow query in production, bad execution plan or bad index?
Here's a timeline of the events you described, as well as my commentary on what was the likely cause of your bad plan.


You're alerted of a slow query that was previously fast


Bad times, I empathize!


You go crazy and run "the forbidden dbcc freeproccache" and it doesn't help


Usually, clearing the cache fixes problems like this if the problem is parameter sniffing.


You drop and recreate a nonclustered index that's being used by the bad plan.  Now your problem is solved


Another reason for bad plans is bad stats.  If the problem is bad stats, then clearing the procedure cache will just result in the same bad execution plan being produced again (based on the bad stats).  

Creating an index on a column creates new statistics on that column WITH FULLSCAN:


  Compute statistics by scanning all rows in the table or indexed view.


These are usually the best stats, because they include the most comprehensive view of the data.

Statistics can be automatically updated over time, as rows in the table are changed / added / deleted.  SQL Server will use different "sampling percents" based on the size of the table.  From that same docs page:


  For most workloads, a full scan is not required, and default sampling is adequate.
  However, certain workloads that are sensitive to widely varying data distributions may require an increased sample size, or even a full scan.


It sounds like what happened was:


an automatic stats update ran for this index, with a low or otherwise problematic sample rate
this triggered the creation of a new execution plan, and that plan was bad
you re-created the index, which produces good stats again


You mentioned you're using Ola's index and stats maintenance solution.  You may want to add a special case for this table / index to update stats with FULLSCAN, as it sounds like the table's data is skewed enough to warrant that.  

If you want to avoid scanning the whole table (I don't know how big it is), you can experiment with different sample percentages (starting at 100, and dropping by 5 or 10 percent until you get the bad plan).



Looking the execution plans you provided (thanks!), you can see evidence for my theory.  Here's the index for the bad plan:

&lt;StatisticsInfo Database="[BDM]" Schema="[dbo]" Table="
                [SubTypeInstanceProcessAdvancements]" Statistics="[AsOfDate]" 
                ModificationCount="288" SamplingPercent="23.4265" 
                LastUpdate="2019-08-15T22:00:09.91" /&gt;


And here's the good plan:

&lt;StatisticsInfo Database="[BDM]" Schema="[dbo]" Table="
                [SubTypeInstanceProcessAdvancements]" Statistics="[AsOfDate]" 
                ModificationCount="0" SamplingPercent="100" 
                LastUpdate="2019-08-16T13:50:10.43" /&gt;



The bad plan has a sample percent of 23.4265, while the good plan had stats sampled at 100% (because of the index recreation).