I never found out if you have to defeat all or just one of them to free the soldiers.
With defeat I mean this: meet them for the first time, before you enter the Wastelands. They are not killed the first time, just chased away.
Wait, you haven't met the imp? Did you free Zandalor? If so, you need to look into the Imp scrying statue, you'll see where he is hiding.
Kiya
