"In addition to not having a sort() method it seems that concurrent_hash_map() doesn't support sorted insertion?"
C++'s map is essentially an ordered tree, TBB's concurrent_hash_map is essentially a hash table. std::map doesn't support hashing, and access has logarithmic complexity, so it's not a one-sided deficiency: you just can't have it both ways at the same time, I guess.

"Can anyone from Intel confirm this, and give a valid reason why such a feature existing in standard hash_map) would be left out in TBB?"
If you don't mind my giving this a try: C++ is getting an "unordered_map" (say what? OMG!), and maybe a concurrent skip list could be considered in TBB's future (but you should check for yourself what has been written about this before, or maybe somebody could remind us).

"Furthermore, looking at the source code, accessors are thread-safe, but what about iterators?"
Do you have an example that makes sense with a hash map? And even so, complexity and performance considerations may require separate implementations without or with concurrent iterators, i.e., concurrent iterators don't come cheap.

"For example, how to advance through a sorted list of items in one thread which is controlled by user input (navigation keys) and add/remove items in sorted order from another thread while keeping everything thread-safe?"
In this situation a conventional locked std::map would do fine: users are so slow you might as well go to sleep waiting for them to do anything, you don't need the performance of a concurrent_hash_map(), let alone anything even faster, all with their own trade-offs between user features and performance.

"I am aware that I am not doing any parallel computation using concurrent_hash_map(), and therefore I am perhaps not using it as intended, but I would still like to have a thread-safe hash_map()."
It looks like you should write your own wrapper around std::map to hide the lock.