I wonder if:

1. VBA collections will be faster?
2. VLOOKUP using sorted array and 'True' as the last parameter. I think this makes binary lookup for vlookup possible. You can search web for shallsort algorithms if you decide to go this route.