I've tried three different strategies with three heroes, and none of them got the last favour quest. It doesn't appear to have anything to do with whether or not you have researched or trained legionaries yourself. It also doesn't have anything to do with whether or not you released Eleuia from her father's clutches.
Then I got a brainwave and realised the legionary is dying, so maybe you should get to him asap, before he dies, so with my youngest hero I went to NK as soon as I could - after only 2 days of playing... and again the legionary was already dead.
In fact, no one in our alliance has seen him this alpha. Is this even still a quest???