Remember that Varis showed up after Thoridan left with the key. So, they were in the area and chose to wait and watch. Now how they kept hidden in the clouds such a huge ship is sheer luck on their part.