I can think of a few ways actually. First of all as a paladin, she's probably had to keep the peace several times in Memphia. As a result she's probably had the misfortune to attend an execution or two. Furthermore as a former soldier, he may very well have been deferring to her if she worked in any capacity with Mephia military. I assume as a paladin she would have done this at least. And outside of his work, Garret can on occasion have been found in a tavern enjoying a drink. Its possible she could have ran into her there incognito.