I remember the episode in which Woof-Woof (Barkley's original name) appeared: Gordon and the kids meet a stray on the street, with no ID except a damaged name tag ("I see a 'W' here, but the rest is worn off...") Gordon, Oscar the Grouch, and some other characters made vain attempts to guess the dog's name. Eventually, Maria (at least I think it was her) called "Here, Woof-Woof"; the dog charged at her, barking loudly.
Barkley got his new name in a later episode; I remember only that several characters argued about whether to change it. (Does anybody else know more about the story?)
As far as an original owner, Mike is right; Woof-Woof/Barkley seems to be everybody's dog until Linda adopts him permanently. If I missed any other owners in-between, I'd like to know...