Exploring the High Seas

12/22/15 Update: A hotfix on 12/22/15 has made the achievement criteria for the mount and heirlooms give account-wide credit. There is currently no indication of this in the UI, but if your account has completed all the rare missions spread across alts, you will now be awarded the achievement upon logging in to the appropriate characters. The bug is now fixed!

NOTE: There is still no account-wide credit for the two missions that reward a pet (Orphaned Animal Rescue) and quest item (Black Market Journal), so you still need to have completed both of those on a single character, but those were never affected by the bug (so that's relatively easy)

The Problem:
It appears the naval missions that reward heirlooms will stop spawning once an account has learned these items. However, the achievement progress is per-character, not account-wide. This means that once you've completed an heirloom mission on two different alts, Exploring the High Seas becomes unobtainable for your account.

The Solution:
Blizzard really needs to make the achievement criteria use account-wide progress to fix this issue.
Please help complain by adding your "same problem here" replies to this bug report forum thread:
http://us.battle.net/wow/en/forum/topic/19648725176

The Details:
I've personally completed over 4000 naval missions across seven characters. My conclusions are based on observations from myself and many others I've spoken to.

Specifically, the rare naval missions that create this problem are:
- [mission=650] (heirloom reward)
- [mission=649] (heirloom reward)
- [mission=616] (heirloom reward)

Note the two missions that reward a pet ([mission=619]) and quest item ([mission=647]), commonly spawn multiple times even for the same character, so those are not part of the problem. There are reports that the mount mission ([mission=615]) can also spawn multiple times per account, although it seems to be significantly more rare.

Also note it is possible (though unlikely) for the same heirloom mission you've never completed to spawn simultaneously on two different characters (and completing one will not remove the available mission from the other character's board). This appears to be the only way to get a "duplicate" heirloom reward and achievement credit for the same mission on two different alts. However this is both unlikely and also not exploitable to obtain the achievement once your account has fallen into the unobtainable status.

Players who have this achievement are usually only those with a single active shipyard on their account - or those with enough luck or foresight to never complete an heirloom or mount mission on an alt. Until the bug is fixed, the best way to avoid falling into this trap is to NEVER complete an heirloom mission on an alt - just ignore that mission on your alt and it will eventually expire (and can even pop on other toons before that, provided you don't complete it).

As of 22/12/2015 this is now Account wide.

https://twitter.com/WarcraftDevs/status/647144284899008512

From what I understand from this tweet it seems that if you're looking for one of the rare missions for this achievement then the best way is to find out where on the map it spawns and focus on doing missions in that area.

I could be wrong but I'm going to give this a try since after over 1000 missions the pet mission still hasn't popped up on my main.