If this is to be believed, the tags were found in the yard; the tags could not be removed without human intervention. It sounds to me like these folks had their dog under control. He was in their yard and somebody came into their yard, removed the tags, and stole him.
In most states, title to property is like water: It cannot rise above its source. If this dog was stolen, he remains the property of the original owner, irrespective of what happens later, absent some statute of limitations.
Why would anybody who is stealing a dog take the time leave the tags on the front lawn and take the collar? Makes no sense. More reasonable scenario is that the original owner did not put the tags on or took them off (maybe they jingled).
Why would somebody steal a nice dog then abandon it on a military base to be picked up? Unless it is an irate neighbor who is tired of the barking (made it up).
Once the base picked up the dog, how do they tell if it is stolen or abandoned? Looks abandoned to me, hard to tell.
I agree regarding stolen property, no act can perfect title on a stolen item. If it is decided that the dog was indeed stolen then the new owners would have to return it.
Regarding statute of limitations, it might be as short as 5 days on a dog. Don't know.
Regarding military base not being cooperative, I think they may know that they have some liability here and hoped the people would just go away.