Why is creating and dropping a random index fixing this performance problem? I have a big heap table with 17,093,139 rows. This table is the most heavily used table in the database. Since this is a heap table, there are only non-clustered indexes in this table. I rebuild/reorganize fragmented indexes on this table regularly. 

Now we are facing this issue very often: Lots of queries accessing this table will suddenly start taking longer than usual. When I check, I observe that the execution plans for the queries have changed. 

I create and drop a random non-clustered index and this fixes the issue. 

What I don't get is, what is causing these sudden slowness randomly anytime and what does creating and dropping the index do in the background to the table to fix it which the index rebuild job doesn't do? 

I need to find what exactly is triggering these slowdowns so that a permanent solution can be found as I can't just just keeping creating and dropping the index to fix this issue every time. 

Any help here would be greatly appreciated.
Dropping an index on your table will flush the execution plan that refer to this table from the cache. (I think the index need to contain a column that is referenced in the query but not 100% sure about that).

SQL then build a fresh execution plan which "fix" your issue.

You could try to rebuild the stats (instead of dropping an index), or drop the execution plan manually (see Sp_blitz store procedures to get the command easilly). You will probably have the same behavior (Query fix). If so, then you may want to read on parameter sniffing issue.

P.s. This is rarelly a good practive to have a table without cluster index. Usually, the only good case I've seen is for log table where you want the insert to be done real quick... but in your case, if you have nonclustered index, you will have overhead for the inserts anyway.