A quick google shows that there are lock-free implementations of AVL trees and red-black trees. And every paper I've ever read about lock-free data structures includes both addition and removal operations.
About 10% of the effort so far has gone into coding the actual data structures - almost all the work goes into testing, benchmarking, performance tuning, documentation, porting to new platforms, fundamental improvements in the basic design and so on. The benchmark app alone has taken all in all about six full months to write. I thought it'd be simple, it turned out to be a tar-pit!
As an aside, binary trees turn out to be really great with lock-free. In the obvious locking implementations, there's one lock per tree. You can use read-writer locks to get parallelism on read, but even so, the mere existance of a single lock of any kind induces memory contention which eliminates scaling as processor counts rise.
I'm sure there are in the locking literature better solutions, but I'm up to speed with lock-free, rather than locking, solutions, so I don't much know about them.
Regarding lock-free, there is no single lock, and btrees are beautiful because they naturally distribute memory accesses throughout the tree. Performance basically scales linearly. There's a gnuplot on the site from a 16 core Amazon VM, and that property can clearly be seen. Every new core simply adds another 200k benchmark ops per second. For the other, non-scaling data structures, new cores are death.