Yeah, for those tempted in these directions, Zip trees seem like the clearly preferred tool. The variable-sized heap blocks of the skip list and the need for 4 pointers per entry (on average two doubly-linked list nodes) turn out to be real limitations in practice. At the end of the day, the only think skip lists really win on is code size.
For those not tempted and wondering if they should be: no, stick with your existing (red/black or AVL) balanced trees. They're clunkier and harder to explain, but they work just as well.
Unless you absolutely require deletion of a node specified by pointer, why would you include backlinks?
(Also, if you’re fine with resorting to randomized data structures, conventional treaps are quite good while being IMO easier to understand and code than either AVL or RB. The only reason I could imagine for not using them is adversarial input, although I’ve never seen an attack demostrated. Now that I’m reading the paper, zip trees seem quite nice and simple as well.)
For those not tempted and wondering if they should be: no, stick with your existing (red/black or AVL) balanced trees. They're clunkier and harder to explain, but they work just as well.