Quoting Tyrion2001,
reply 3
What they could do is make it part of a quest for when the hero joins you. So when the hero joins you he could say on a recent exploit his sword was lost on some cave doing battle with x beast. It then makes finding the magic item that belongs with the hero less a matter of luck and more performing a quest.
Quoting Denryu,
Yes this is what I had in mind.
The hero could also make retreiving his sword a condition for joining you, or alternatively you could get a quest to find an item, not knowing what the reward was, and after retrieving the item the person you were doing the quest for turns out to be a hero...
In addition to great back story and special quests, it would be great if Heros would offer join you empire depending on your relative strength/weakness, magical affinity, etc.
For instance, a specific Hero would offer to join only underdog kingdoms/empires, because (s)he loves helping the weak. As said kingdom/empire grows it would cost more to keep this hero happy and eventually the hero may leave, because their services are no longer needed.
In a magical instance, a Hero could love a Channeler who uses Fire magic. If your know Fire spells stayed in a high enough ratio to your other magic the hero would remain (and perhaps give you a bonus to fire spell research).
With creatures this could be much the same. Maybe a red dragon has a higher chance of being tamed by a Sovereign with high fire magic abilities.