There are several Lock-Free Quese available, http://www.cs.tau.ac.il/~shanir/nir-pubs-web/Papers/FIFO_Queues.pdf, Nir Shivit is a very prominent wait-free/lock-free algorithm developer. libCDS,libcds.sourceforge.net, has an implementation of it that may be useful.
Unfortunately I need an application to test performance increase on replacing tbb concurrent hashmap with my Wait-Free hashtable. If, as you describe, the concurrent hashmap is not used much, then this is not a good fit for testing my hashtable.
Thanks for your replies, and good luck on your server.