Have you not heard the stories? Captain Barbossa and his crew of miscreants sail from the dreaded Isla de Muerta. It's an island that cannot be found except by those who already know where it is. http://pirates.wikia.com/wiki/Isla_de_Muerta

Except that's easily solved, by going there with someone who's been there before...

How did your guide get there the first time?

It's guides, all the way down.

Isla Muerta is a piece of continental earth which has been slowly drifting away from the continent for generations. The guide's ancestry has lived there since before the island was an island.

He was born there?

He was hatched by the first chicken.

How did his parents get to the island? Were they born there as well? If so, how did the first settler found it? Or is this island the origin of life on Earth?

It doesn't say the the island was always findable only by those who already know where it is. This could have changed at some point.

True. Also most islands are younger then life on Earth, so the island could just appear under the first guide.