I presume you've done Copy + Paste Special->Value wherever you can.
My next step would be to look for calculations that don't need to be repeated. If the MATCH is only needed once per column, it would make sense to remove it from the INDEX formula into a single cell and then reference that cell. If that doesn't work for you, perhaps you could rewrite the formulas to perform the searches over smaller ranges?
MATCH is much faster when it does not have to look for an exact match in unsorted data: when the match-type argument in =MATCH(lookup-array, lookup-value, match-type) is 1 or -1. This requires that the data in lookup-array be sorted. Use 1 when the data is sorted ascending, -1 when the data is sorted descending.
If you're looking for only a few INDEX+MATCH values, the DGET function is wickedly fast. Its drawback is that DGET requires extra worksheet space to set up the search criteria. If you've used Advanced Filters, then the setup for DGET and the other D-functions (DSUM, DCOUNT, DMAX, and so on) should be familiar.
VBA could be an option. We know Autofiltering in Excel, where you use Data >> Filter from the ribbon, is quick. Most of the functionality of Autofiltering is available in VBA. Searches can be performed quickly in VBA using Range.Autofilter. You can also perform Advanced Filtering through VBA.