Just keep checking back with him and Lola. I don't think you can complete the quest unless you read every letter so just keep going between the two locations and you will eventually get the item.

After you get Terra back, you have the option to wander the world with the airship but after you start the plot again you won't have the option again until the Floating Continent appears.

As for Cid, I feel the reason why there is no reward for saving Cid is because Square canonically believes he dies and the reward-less scenario of saving him is to tell players its okay to kill him off.

As for the island being a haven for the party, the party already has their base of operations in the Falcon so I don't see it being necessary.