+1 to the type-sorted approach.
Dynamic dispatch is not very cheap (and has nontrivial cost even with vtable), so one way is to hoist the dispatch out of loops, making it static. That could work via typesortedcollections, or alternatively Dict{Int, Tuple{Vector{LJPair}, Vector{MiePair}}}, or alternatively Tuple{Dict{Int, Vector{LJPair}}, Dict{Int, Vector{MiePair}}}.
A very situational approach I made ok experiences with is the following: Have Dict{Int, Vector{UInt32}} (choose integer size depending on alignment of your real data), and just serialize and parse my data into this vector. In my application, the true type would have been Dict{Int, Vector{NTuple{N, Int32} where N}}, i.e. inhomogeneous in the tuple length. Since I did not need the full 32 bits everywhere, there was the possibility of stealing some leading bits to signify the lengths of tuples, and also compress the serialized storage.