Update Statistics with full scan for a single table
While you could schedule a job to run UPDATE STATISTICS on that particular table, you should also look into Parameter Sniffing. What's likely happening here is that a bad plan was wiped from the plan cache when you updated statistics on that table. Instead of doing a costly UPDATE STATISTICS, remove the bad plan from cache. Once wiped from the plan cache, the query will compile and get a new plan. Whichever parameter values were used at the time of compilation is what the execution plan will be optimized, that is as long as you are not overriding that behavior with the OPTION OPTIMIZE FOR query hint.

If the search function is a stored procedure, you can use the good ol' sp_recompile. Otherwise, use DBCC FREEPROCACHE and pass that command the SQL handle or the plan handle. You can use sp_BlitzCache with ExpertMode = 1 to get the command (it's all the way to the right in the result set).

To help diagnose which plan is causing the issue, I like to use sp_WhoIsActive or sp_BlitzCache. For sp_WhoIsActive, I like to log current activity to a table and then I can go back in time to compare execution plans and see who was the culprit.

For more information on Parameter Sniffing, see Erland's Slow in the Application, Fast in SSMS? post.