Returning a character to your hand is not a cost, so the character will remain in play if A Mission in Essos is cancelled. In fact, since you are not required to “choose” a target for this ability, a cancel can only be used before the choice is even made.
The character can be saved from leaving play (by a duplicate, for instance). If that happens, the post-then aspect of the effect does not resolve, so you cannot search for anything. (See The word "Then".)
You can search for a character with the same title as the one you returned to hand, but it can only be a version with lower printed cost.