Just returned from her fourth voyage around sectors 5,6,7,8. It's like sector 09 doesn't exist, lol.
She has Enterprise Forecastle and Enterprise Hull. Tried different combinations like 5->6->8->7 and 5->7->8->6, with no luck discovering sector 09.
But we discovered island 10 from our first trip to 7->8, and it was even without the Enterprise Forecastle.
Now she's rank 27, and it looks like this:
http://imgur.com/UolJC9N

All of the previous sectors were unlocked within one or two trips around their vicinity.
So I would say that RNG factor here is rather big, maybe it even grows with island ranks.