Do key-dependent S-boxes make efficient constant-time software implementations almost impossible? It seems to me that algorithms like Blowfish and Twofish with key-dependent S-boxes are almost impossible to implement without table lookups, and thus are almost impossible to implement in software without being vulnerable to timing attacks (other than by linear search through a large array, which is much, much slower).  Since these algorithms are also ill-suited to hardware implementation (since the S-box must be stored in RAM), this seems to make the algorithms suboptimal for all purposes.

Is this assessment correct?  It seems strange to me that I can come to such a strong conclusion.  Yet I cannot think of any way to (reasonably) implement key-dependent S-boxes in constant time, so my point seems to still stand.
The point in the question makes senses, especially if one restricts to portable software implementations. But:


Small or moderately large constant-time RAM tables are reasonable, efficient, and (thus) common hardware building blocks. They are often used in DPA-protected DES and AES hardware coprocessors. Thus we can't dismiss key-dependent S-tables in hardware.
When knowing and controlling one's CPU well enough, constant-time table lookups are often possible (e.g. if there is no cache for data RAM, as is the case on many embedded CPUs).
There are other conceivable methods to guard against purely timing attacks, including releasing results with a fixed delay counted from start of computation, e.g. with the help of a hardware timer (however there often are other side-channels than pure timing, and that complicates things, a lot).