Stored Procedure: table-Value parameters
Check out this post from Erik Darling: 

Table Valued Parameters: Unexpected Parameter Sniffing

The gist of it is that table-valued parameters are susceptible to parameter sniffing just like other parameters.  If the execution plan happened to get cached when 2,000 rows were passed in via the TVP, then that's the plan you're stuck with (until a recompile).

All of the usual solutions to parameter sniffing apply.  It would be helpful if you could provide an actual execution plan and query text to get a better idea of what's going on.

Probably the "simplest" solution is to add a RECOMPILE hint to the query that's performing the join to this big table.  This will incur higher CPU (due to more plan recompiles) and you lose the "predictability" of the query plan, but it could solve the immediate plan quality issue.  

This should also help with the problem of fixed join estimates, mentioned in Erik's post:


  Non-join cardinality estimates behave like local variables (fixed estimates)  
  
  ...we get 10% for equality, 30% for inequality, and 9% for two inequalities.