Still wholly theoretical, but I was watching the AH like a hawk at about the 18 hour mark since the update went live, just in case the New World Macrame was from the airship missions. Sure enough, about 21 hours after the update, three New World Macrames got put up on the AH.

Purely speculative, but I'd say it's a very solid chance that New World Macrame comes from exploratory missions. Which one and how rare remains to be seen.

And now to the next mystery: what level recipe and what class is the New World set crafted from?