The look up table is not all that huge.
I made DES hum on one of IBM's pieces of equipment, the 4700 bank branch controller. The look up table, which I implemented in assembly language gave it close to 7x performance boost compared to prior version. To be fair the processor was some 30% faster.
Look up IBM Research's Lucifer project to see more on S-boxes. No connection to to 666! :)