The city water main shut off is in the front yard of our 1960s home that we've lived in for 15 years. A few decades ago, the previous owners filled in that part of the yard with a lot of fill to level it out – we were not made aware of this until a neighbor recently told us. Now our inside turn off valve is leaking and needs to be replaced - it's just a pipe coming up from the basement cement floor with a simple knob. The city can’t locate the main shut-off in the yard probably because it’s too deep for their metal detectors and they have no map of where it should be located. To start digging could cost us thousands. I’m wondering if title insurance should be covering this? Anyhow, is there some way to install a new shut off valve in the house without shutting off the city water line coming in?
Freeze the pipe
I've heard tales of stopping a pipe for valve replacement by freezing the water but I haven't ever attempted it. Take this as an entirely untested theory. I suppose it might go something like the following.
Choose a location on the pipe sufficiently far from the valve to be replaced and pack dry ice around the pipe. It's probably a good idea to freeze a section several inches long at minimum. Have sufficient quantity of dry ice on hand to maintain the frozen section for longer than it takes to bring more dry ice, just in case things go horribly wrong and you need to maintain it frozen longer than expected.
Procedure could vary depending on whether the new valve can thread on to an existing adapter or pipe end or whether it's necessary to solder something (in the case of a copper tube service line).
There are plenty of risks involved, mostly distilling to "what happens if we get the old valve off but water gushes through before the new valve is in place?" I can't give advice on that, but I could suggest that you test the technique first. Freeze the pipe, but instead of proceeding with the valve replacement, open a faucet and wait to see how much working time the freeze provided.
The one-call 811 service won't mark private facilities but they should mark at least the city-owned pipe coming from the street. Unfortunately the markings would be made by the utility owner (or their contractor)... so if the city water department already can't find your pipe, 811 may be no help. At that age your service line is almost certainly metallic so a locator worth their salt should be able to connect a transmitter to the line and locate it. Private underground locators also exist but I can't speak to their cost. In any case, merely having the line marked doesn't tell you where along the line the valve might be buried.
The city will have shutoff valves in their mains. They're frequently found at intersections. You may be able to negotiate with the city for a half-hour shut down of the section your house is connected to.
Finally.. (bear with me here) maybe it's time for an upgrade/replacement of the service line. It could be made of lead pipe, it could have corrosion built up inside it, who knows. It might be cost effective to have a new pipe installed with trenchless boring techniques. You get the new line into the house and plumbed to a valve, then let it be the city's problem to locate where your existing line connects with theirs and make the change. After the switch-over is done on their side you can freely disconnect the house plumbing from the old leaky valve and connect it to the shiny new valve and supply line.