Have you tried bringing the dog to a vet to be scanned? Perhaps the owner's had sense to put a microchip in it in the case that he became lost, like we did with our cat George.
As unfortunate as it sounds, he may not have been stolen. I knew a dog (a Rott) who had been tied to a post outside a trailer, day in and day out, for years. We thought she was being treated kindly..until one day they came to their neighbours asking to keep an eye on the place while they went for vacation- well they left the dog there, tied out, with no food!
And they were leaving for three weeks! Apparently this was a regular occurance, that she was a "guard dog" and that was it. This dog who looked healthy from a distance was actually bone-thin, abused and trembling. She was taken from them by the neighbours and made a great pet.
However...the recent spay marks...maybe a vet in the area or clinic has performed the spay? I wonder who performed spays on that type of dog in the area? I'd be willing to call around and help!