If you don't mind doing it in Trammel, do it this way:
1. Use a char than can gate even if they need +magery on jewels and a book
2. Mark a rune *inside* the Orc prisoner cell
3. Ideally, lock the run down beside a Crystal Portal in you house (vet reward and you probably have one already)
4. Cast Gate on the Orc cell rune, walk through, double click the prisoner and accept quest. Ignore the guards - they will barely have time to target you before you are gone.
5. NOTE WHICH TOWN HE WANTS TO GO TO
6. Walk back through the gate before it closes. The prisoner will follow you
7. You are now beside your Crystal Portal. Simply say "whichever town mint"
8. You will be transported to the selected town and the prisoner will follow you.
9. Walk a few steps and you will get the reward message - except Yew where you will have to lead him towards the town proper.
It literally take 5-10 seconds to complete. Repeat this 5 times a day at 5 minute (I think) intervals.