Purely functional, total implementation of ST/STRef?

I showed somebody a signature for ST and STRef in OCaml, to demonstrate the scoping trick. Later he asked if it could be implemented without real mutation, even inefficiently. The only ways we have thought of use features of OCaml that actually use mutation under the hood, and they used partial functions. Has anybody done this in a satisfying way? Fancy type system features are allowed.