The Horde version of the Nazjatar quest "Scouting the Palace" (quest id: 55481) should be offered by Lor'themar Theron in Newhome after completing the quest "Back out to Sea". I have already completed "Back out to Sea", but Lor'themar Theron still doesn't offer "Scouting the Palace".