My plumber this week literally bulldozed the entire backyard between the last inspection point and the connection out to the mains. I have a strange feeling he didn't bring one of those cameras ... but that does seem the most logical way to find the buggers. Bulldozers are a bit brute force, but it certainly worked in this case.
Add to the confusion with this old house we found a lot of wiring encased in galvanised pipes, which were the same as the old water pipes, and both going in about the same direction. At my old house they had plastic water pipes and sure enough, the power to the shed was in the same damn plastic pipes. Argh!
ETA: we were telling the difference between the two kinds of pipes by turning on the tap, sticking an ear on the pipes and listening for the water going through them.