Why don't table lookups run in constant time? The Wikipedia article on big O notation says that performing a lookup is a constant time operation. So why are lookup tables susceptible to timing attacks?
It mostly has to do with the real world influence of memory caches.

A cache is a small amount of fast memory; when you read from memory, the contents are placed in this fast memory (possibly along with adjacent locations); if you read from the location again, you read it from the fast memory (which, of course, proceeds much faster).

Hence, if you read a location that you've read before, it goes much faster than if you read a location which you haven't; hence, you're not constant time.

Modern CPUs can process data much faster than memory can respond (perhaps by a factor of 100), hence caches are pretty much ubiquitous.  Some lower end microcontrollers might not have them; but they're an exception...