Not just probably, absolutely. Skip lists are probably pretty balanced, which is always less balanced than actually pretty balanced. Their sole claim to fame is their simplicity in implementation compared to actual self-balancing trees.
First, there's the approach everybody remembers from Intro to Algorithms: use a binary min-heap. It's guaranteed to be balanced, so you get O(lg n) time insertions and delete-the-minimum operations, with low constant factors. Nice! But how do you make it concurrent? You can put a lock on the whole thing and only let one thread use it at once, but that's slow. You could use fancy fine-grained locking, but there will still be inter-thread memory conflicts arising from the heapify operations you need to maintain the heap invariant. There has been some work on this, and they've come up with some decent ideas, but it still has scaling problems.
Now look at skip lists. It's a randomized sorted list data structure, and it claims to be, as you put it, probably pretty balanced. Various threads can insert concurrently without breaking that "probably pretty balanced" property. The memory read- and write-sets are very local, and it's possible to do all this with lock-free synchronization. The end result is a priority queue data structure that scales to hundreds of cores. And the code doesn't fry your brain, which is a plus. There's a pretty neat paper about it here:
http://www-cs-students.stanford.edu/~itayl/ipdps.pdf
By the way, if you happen to be using a processor with hardware transactional memory support (you aren't, yet), then this code becomes even easier to write, as you don't have to worry about how to do lock-free synchronization. I almost felt cheated by how simple it was.
That said, future HTM systems have a lot of potential, and I think we'll see them come into wider use eventually. The main problem with them seems to be that existing software ecosystems aren't written with HTM in mind, so you get pathological memory access patterns slowing things down. But with some minor enhancements to the HTM design (like a load instruction which immediately adds its destination address to the write set of a transaction) and compiler and runtime support, and a reasonable set of concurrent data structures, HTM can absolutely fly.
http://www.cl.cam.ac.uk/research/srg/netos/lock-free/
(That's a lock-free red-black tree impl).
But I can't see why the same cannot be done using trees. :-/
Judy arrays came up once too; there's a really excellent critique of Judy arrays here:
http://www.nothings.org/computer/judy/
(Long story short: you can get comparable performance from a straightforward hash table, and Judy Arrays have to be tuned to the microarchitecture).
Favorite data structure not cited here:
Aguri trees, which marry a bounded-size radix trie (like you'd use in a software routing table) to an LRU list, and automatically synthesize aggregates (like, 10.0.0.0/16 from 1,000 observations across all IPs) from the pattern of insertion. They're best known in traffic analysis, but we've used them on in runtime memory analysis as well.