"Immutable" data structures is rather confusing name. Here it is a synonym for persistent data structure [1], which means that you operate on data structures by creating new "versions" of them, which share a lot of memory with the old versions. Parts of the program that refer to the old version see it as immutable.
Modern radix trees[1] can be as fast as the hash maps you'd find in a language's standard library while providing additional capabilities (ie fast ordered traversal). Making them immutable and persistent[2] is easy and only adds a bit of performance overhead.
Obviously programs that rely on communicating by mutating parts of a dictionary would have to be rewritten to use an immutable, persistent map—but they could still maintain similar performance.
On the other hand, stating "they could still maintain similar performance" for immutable dictionaries is misleading at best (you are right for dictionary sizes approaching 0). Anyone can look up benchmarks on the Internet showing real-world performance of immutable data structures and make their mind up if they actually can deliver in their particular use cases.
Mutability could be always used to boost performance on Von Neumann architecture if you know what you are doing. It's just becoming impractical due to increased complexity, pervasive security paranoia and the fact that there are very few people that can get things done right. If you want to contribute to advance your case, please create a competing computer architecture as fast as Von Neumann's, physically possible, but based on immutability.
Well, opt-in immutable dict would be awesome. I've found that many times my usage of set and list is more appropriate as their immutable counterparts (frozenset, tuple). Lots of times I create sets or lists with the intention that they be immutable and it would be clearer if I could specify to future me/maintainers/extenders that this should remain as initialized.
