For Sea of Clouds, do the Airship rides count as passing through the zone border? Give it a shot, I'm a loner, so my instance number has never been an issue, but perhaps the Airship will get you into the right instance.