> IIRC, the only way to address the issue was the addition of the AES-NI instruction set, which came a few years later.

Another option would be to use a bitsliced implementation of AES, at some cost in speed. I could also imagine an implementation which read the whole table every time, using constant-time operations to select the desired element(s), but I don't know how slow that would be.