For me, finding the islands were pretty easy. Though I only took time to travel around towards the end of the game, even when I came up to a Malboro at times you can't be quick enough because if you have a high level character and the monster casts a spell on it, it makes you attack yourself/another player, killing it. I've always hated Malboro's for that, but then they're such a cool monster.

Anyway, good luck finding the islands.