They are pretty useful for certain kinds of program analysis (like abstract interpretation and symbolic execution) where you need to create slightly modified copies of the program state (e.g. when you need to split the state on a conditional, or merge two states). Immutable data structures are (space) efficient for this use case. Moreover, you can combine them with hash consing for more space efficiency (only if you are creating lots of objects that share most of their data) and fast equality checking where there is only one copy a value in heap so equality checking is just object identity checking and addresses work as hash values now so hashing large objects is faster too.

The algorithms used in these analyses are usually described in terms of mathematical objects which are inherently immutable and using immutable objects makes correctness proofs easier.

When writing a piece of code, I start with immutable data structures because of the ease of mind they bring to the table (you can pass them around and you know they will not be modified so it makes reasoning and debugging easier, this is less of a problem in C++ because it has const references and const methods). Then, if an algorithm needs a mutable data structure or if the immutable data structures are too slow (e.g. the code is in the hot path) then I switch to mutable data structures. I think it is just a different mentality when approaching programming. It works for me because (a) it is the norm in my field (program analysis, or programming languages in general), and (b) I use a programming language with an ecosystem around immutable data structures (Scala).