Veritas
Very fortunately, they are not searching for a "mysterious stranger" type who lurked in shadows and spoke to no one. That's not the Paladin style. Derne's approach was much more classic, outgoing, "Hello Good People Of Veritas!".
A few of the old folks here certainly remember him.
"Oh, a Paladin," one elderly woman says, seeing no reason to beat around the bush and talk about symbols of the order. "That's what that insignia means, you know, a Paladin, like the young lady over there."
She points out Mae, who comes closer so that she too can hear who is talking about Paladins.
"You know we don't see them very often," the old woman says.
"I'm sorry," Mae says. "There aren't many of us."
"Oh it's nothing like that," the old woman replies. She's one of those small, lithe and bony old women who seem to have a lot of living left in her. "I know about Paladins, and they don't come when they aren't needed or called, and we've had no real need."
"But there have been Goblins, and other foul creatures in the wild lands, we've heard," Mae says.
"Yes, this is true. But nothing the people of Veritas haven't been able to deal with. Having Gold Dragons patrol on occasion helps. So does Calphi, she seems to know the ways of Goblins, and she can often predict what they'll do when they've been seen around. Very smart. So there are some dangers in the wilderness, but threats to Veritas itself... very rare. But Derne came anyway. He wasn't looking to defeat any foe in particular, he was very interested in our water. You've heard, perhaps, that Veritas's lake has... properties?"
"It is like Holy Water." Mae says.
"So they say. Derne wanted to find out why- what was the source of this power. I think it led him to seek out the source, literally. The source of the water in the lake. He talked to some of the trappers, and spent some time with Calphi, asking a lot of questions. Then Calphi took him across the lake on her boat, and he hasn't been back."
"He could have run into trouble of any kind, out there," another of the old folks says. "Sure, he's a Paladin, but he was young. Easily could have bitten off more than he could chew. Paladin or no, you don't explore out there alone, or unless you know exactly what you are doing."