5000 item limit prevents opening item even if view works fine

I have a Sharepoint task list with 5001 items in it. I have talked with the department that uses it about limiting the size by clearing out old items, but that is probably a little ways off.

When I ran into the size limit, I increased the limit temporarily and added an index and then brought it back down to 5000. That worked fine to allow me to view the list. However, I could not open an item from the list to edit it unless the view threshold was brought back up above 5000.

What is the solution for this?

I should say that this particular list is used by about 10-15 people at a time, max.