In theory when you come down from the airship she should be just slightly south of the little shop section of the calm lands where you appear. Originally she was in the north west right?

If you can't find her somthing must have gone wrong with your save. Hope this helps.