When you say immutable, do you mean that it should be set once and never allowed to be changed?
One option, if you have this one to one immutable relationship between user id and vault id is to let the user id also be the vault id. Or a hash of the user id if that makes things easier.
Another option if you really need to be able to set the vault id for a user:
Build a canister that exposes an endpoint for setting/creating the vault id for a user
Assign the blackhole canister as the only controller of that canister
Now that smart contract and the data it holds can never be changed
(You can of course keep calling the canister endpoint to set/create new vault ids)
Situation is simular to that on Ethereum. If you want immutable data, make the smart contract immutable.
The only solutions I know of when it comes to immutable data, not related to smart contracts, is Arweave. And, possibly IPFS, but that data is not permanent.
In theory, you should be able to use Arweave as a storage layer from ICP, haven’t seen anyone attempting it though.