It appears many merchants have taken the idea of lockers from Valkyre and have gone across the world to share in the technology... and to make a killing.
There will be one room on each continent, does not mean it is in town, that will have a sign in the description of the room. There is only one new room in Sloth that has been created for these lockers, the rest were rooms already in Sloth.
To find the lockers, "look sign" will probably be your best bet at finding the rooms. They shouldn't be too hard to search out.
Hopefully this helps out when immortals can not make vaults right away for the players.
Enjoy,
Tox