I think the ! concept you outline has some appeal because it requires us to treat state change as a specific entity- Maybe then it would be possible to have a way to turn it on or off for a chunk of code in order to have enforced purely functional code (sorta like in Haskell, but at runtime)
I could envision something like:
(= x '(2 5 3 4 1))
(def foo ()
(sort! < x))
(w/out-mutation
(foo))
***ERROR- FORBIDDEN EXTERNAL MUTATION IN FUNCTION (FOO)***
Of course, there would have to be an ability by the compiler to automatically substitute code using this construct to do something more efficient when mutation is permitted.