After receiving the quest from Rhagaea, I hunted down Melkea. Melkea gave me the spiel before the battle about my being another one of Rhagaea's lackey bounty hunters and that she would make an example of me.
I won the battle and Melkea showed up as though she would now be my prisoner BUT she gave me the exact same spiel and then just went away.
This scenario went on for another four encounters with the same result.
At this time, Melkea is not in any location that the encyclopedia says she is.
It may just not be working anymore in 1.4.3 beta. That would be ok and no surprise there.