Sql server full text search performance slow with additional conditions or clauses

We had a performance problem with SQL Server (2012 Web). When we have additional where conditions to our full-text Contains search it becomes over 1000x slower, the execution plan changes to a nested loop around the full-text search, and "Actual Rebinds" on the "Table Valued function [FulltextMatch]" went from 1 to 3628.

We noticed that it only happens when full-text searching newly uploaded data; and furthermore, when the full-text search had an additional where clause selecting only the batch of newly inserted records.


Diag 1. Notice the "Table Valued function [FulltextMatch]" is inside a nested loop, with 3628 rebinds. This isn't going to end well.

Our first thought: The full text index hasn't done an incremental update; so we did a Full repopulate index... No Change in performance.

Then I finally found an article that seemed relevant: "First: Make sure that your statistics for the table's index are up to date."

So, I looked up how to do it: 

https://msdn.microsoft.com/en-us/library/ms187348.aspx
https://msdn.microsoft.com/en-CA/library/ms174384.aspx

Steps:
#1) Check when the tables index statistics were last updated on one of the table's indexes:

DBCC SHOW_STATISTICS ( "Table_Name_Here", PK_Table_Name_Here_Index) ;

And found that the date the stats were last updated was before  we had inserted our new 3000 record set into the table. ( The index stats showed there was about ~3000 fewer rows than "actual" )

#2) We updated the index stats manually via:

UPDATE STATISTICS Table_Name_Here

And now, our full-text queries are all lightning fast, regardless of any added where clause and in the execution plan, our "Actual Rebinds" on the "Table Valued function [FulltextMatch]" went back to 1.


Diag 2.  "Table Valued function [FulltextMatch]" now with a rebind count of 1 ( Its not inside a nested loop any more )

And now, to answer the underlying question: 
Why weren't the tables index stats recalculated after the new data was entered? We're assuming at this point that it wasn't a sufficiently large insert to trigger the stats recalculation ( we inserted around 3% new rows ).

Perhaps in this case, the table just needs to have its stats recalculated manually since its a relatively small insert, but has a really high impact on full text search speed when not completed.