REST API Throttle Limit Error

I have an application I built in SharePoint Online which uses REST API queries to pull records out of a SharePoint list which has 400k records. The list has an indexed column and for the most part the values returned in the index column never exceed 5k. The front end has a drop down with the values available in the indexed field. Upon selecting a value the results are returned. This works great.

The issue I’m seeing is that it is possible that occasionally one of the indexed values will exceed the 5k limit which breaks the query if you are querying on that value. My initial thought was that if I go back into the data and reduce the count to below 5k on that index that the application would then allow me to query on that value again.

In my test case, I exceeded the 5k limit on one of the indexed values, breaking the application when I query on that value. I then removed all of the records for that indexed value in the source list, but the application still throws the SPQueryThrottleException error even though no records for that index exist. Is there a way around this? Will that indexed value be broken forever once it’s exceeded?