Sam,

Think about the possibilities of leaving the story somewhat unanswered and mysterious. Don't let on that it's about Asta - but combine the loss and return of Asta with the mystery of who this woman really was.

She claimed she was the daughter of a famous violinist.
A yellow coat she wore that night.
We had a little chat she accused me of -------(referring to preference for men)
Then on a walk disappeared right out of sight.

etc. etc.

Could make for a very interesting lyric - combining mystery dog thief with Asta.