[bob1029]

> that we're somehow getting something for free.

The splay tree also falls squarely into this category for me. The core bit:

> [...] splay trees can take better than logarithmic time, without requiring advance knowledge of the pattern. According to the unproven dynamic optimality conjecture, their performance on all access patterns is within a constant factor of the best possible performance that could be achieved by any other self-adjusting binary search tree, even one selected to fit that pattern.

I've been iterating a kind of append-only log + database system using this as a technique to optimize I/O patterns. Many forms of storage are very happy when you feed them sequential bytes and prefer reads from more-recently-written physical blocks.