If the lord you want to rescue is being held in a castle, you must speak to the village elder of the village associated with that castle. e.g. Ryibelet for Ryibelet Castle. If the lord is being held in a city, you can speak to village elder of any village associated with that city, e.g. Chaeza for Veluca or Ayyike for Reyvadin. And you must whack the prison guard or knock him out, which seems more humane to me. I almost always take a heavy military hammer for rescue missions.