Should I refresh query plan cache
Lets take your problem step by step:


  It has been running great until one fine morning I pushed a lot of rows to a table that is heavily used and since then I was getting query timeouts.


Whenever you do large updates/inserts to you tables, highly recommend to update stats and reorg/rebuild indexes. That way query optimizer does not select or produce bad plans on wrong estimates.


  In order to fix the problem I run the Database Tuning Advisor and I added some Indexes and Statistics.


Never do that without understanding your workload and proper testing the recommendations. Refer to Don’t just blindly create those “missing” indexes! by Aaron Bertrand.


  I also created a maintenance plan to rebuild indexes daily.


I would recommend you to look at the fragmentation ratio of the indexes and accordingly reorganize them or rebuild them. Best is to use SQL Server Index and Statistics Maintenance as it is best free software out and implemented widely.


  Next, life forced me to clean up the table in matter, and the amount of rows in it is even smaller now than it was before but the timeouts are still happening. So, I removed all indexes that I created and now the website is much more stable but from time to time I still see some timeouts.


Same as above. Now the optimizer has wrong statistics and hence inefficient query plan can be produced. Best is to UPDATE STATISTICS and mark that table for recompile using sp_recompile , so next time the optimizer will generate new plan based on updated stats available.

Also read up on : Slow in the Application, Fast in SSMS?