<p>I recently came across the data structure known as a <a href="http://en.wikipedia.org/wiki/Skip_list" rel="noreferrer"><em>skip list</em></a>. It seems to have very similar behavior to a binary search tree. </p>

<p>Why would you ever want to use a skip list over a binary search tree? </p>

From the
Wikipedia
article you quoted:
Θ(n) operations, which force us to visit every node in ascending order (such as printing the entire list) provide the opportunity to perform a behind-the-scenes derandomization of the level structure of the skip-list in an optimal way, bringing the skip list to O(log n) search time. [...]
  A skip list, upon which we have not
  recently performed [any such] Θ(n) operations,
does not
  provide the same absolute worst-case
  performance guarantees as more
  traditional balanced tree data
  structures
, because it is always
  possible (though with very low
  probability) that the coin-flips used
  to build the skip list will produce a
  badly balanced structure
EDIT: so it's a trade-off: Skip Lists use less memory at the risk that they might degenerate into an unbalanced tree.