There was once a superstition that witches couldn't cross water. Rowling even references it in regard to her choice for the Hut on the Rock in Sorcerer's Stone. I can't recall anywhere in Cannon that directly confirms the hypothesis I'm about to offer but through putting two and two together, I will offer up this answer.
Your assumption that because he can fly, he shouldn't have trouble Apparating over water, is false. A witch or wizard can't Apparate across sea water (maybe all water) no matter how powerful he/she is.
The relevant part of the quote you provide is,
feel Voldemort flying through the sky from far away, over a dark and
stormy sea, and soon he would be close enough to Apparate to them,
and Harry could see no way out. (p. 383)
For most, the part I highlighted only means apparating can't happen over long distances, but when taken in the contextual combination with the detail that he is coming from across the sea seems to at least partially confirm my hypothesis.
Other dealings with crossing water in the books that come to mind include:
- Hagrid's appearance on "The Rock" in Sorcerer's Stone. We know he got there using magic, but we don't know exactly how he got there
and we do know he is not able to Apparate on his own anyway.
Although this does not confirm my hypothesis, it also does not refute it either. In fact, Hagrid even offers that he "flew" to the rock making it pretty likely he did not Apparate there.
Relevant Question regarding Hagrid's visit to the Rock
This is also the occurrence of Rowling's mention of the superstition
Even though Petunia was raised alongside a witch, she is remarkably
ignorant about magic. She and Vernon share a confused idea that they
will somehow be able to squash the magic out of Harry, and in an
attempt to throw off the letters that arrive from Hogwarts on Harry's
eleventh birthday, she and Vernon fall back on the old superstition
that witches cannot cross water. As she had frequently seen Lily jump
streams and run across stepping stones in their childhood, she ought
not to have been surprised when Hagrid had no difficulty making his
way over the stormy sea to the hut on the rock.
[J.K. ROWLING - POTTERMORE - VERNON AND PETUNIA DURSLEY]
While, Rowling is saying witches and wizards can cross water here, it still may hint at the idea there is something about water that is different than the land for witches and wizards anyway. Often, superstitions and rumors include nuggets of mistaken truth. Perhaps, this is a case of mistaken understanding. They can cross water, just not through apparation. Again, a hypothesis.
- Occurrences of travel to or from mainland Europe are not
presented as any easier for Witches and Wizards than for Muggles.
When the Weasley's travel to see Charlie it is a really big deal and
sounds very similar in terms of logistics to what it would be for
others.
The friends that pick up Hagrid's Dragon aren't just
Apparating themselves to Romania (hence being able to fly by and pick
the dragon up. If they were Apparating, they would not have been able to help Hagrid with getting the dragon out of Hogwart's). . . Even if they couldn't Apparate all the way there, they could Apparate to Calais, then Brussels, then Frankfurt and so on. Instead, they choose to fly all that way by broom? Especially with the turbulence created by thermals and the chill over water, that is just crazy if there is another option as simple as Apparating across the Channel - although it was handy for the triumverate of young magicians and Hagrid that they were flying because it solved a sticky situation for them.
Likewise, though not explained in detail, the logistics of getting foreign members of the community to both the Quidditch Cup and the Triwizard Tournament are not generally presented as points in time when many of those from the mainland chose Apparating - though, admittedly there may be a host of other reasons for such a choice.
- The trip to Voldemort's Cave (for the locket) is the most important piece of information I have supporting my theory. Dumbledore
Apparates Harry and Himself to near the cave, but they do have a harrowing and wet adventure actually getting there. First they Apparate to a ledge along the cliff face which Dumbledore describes in the following way to Harry once there.
"I imagine that Riddle climbed down, Magic would've served him better
than ropes and he brought two small children with him, probably for
the pleasure of terrorizing them. I think the journey alone would
have done it, don't you?" HBP Page 556.
They look down off the cliff face to see a fissure in the wall of cliffs and the sea below.
"You see?" said Dumbledore quietly, holding his wand a little higher.
Harry saw a fissure in the cliff into which dark water was swirling.
"You will not object to getting a little wet?" HBP Page 556.
when they get into the antechamber to the cave, Dumbledore says,
"Now it is Lord Voldemort's obstacles that stand in our way, rather
than those nature made." HBP Page 558.
Indicating that he couldn't just Apparate to the ante chamber (or walk right in) because of nature made obstacles and not magical ones. It is easy to conclude it is the water that serves as the obstacle - as cliffs do not provide obstacles for someone who can Apparate given the fact that they can apparate from the astronomy tower. Apparating into and out of buildings is possible (when not protected by other charms) so it isn't a problem of the rock walls being in the way either.
- Other than getting to and from Azkaban, I can't think of another
occurrence of a need to get across water when Apparating might have
been a choice. Perhaps Azkaban's location out at sea is part of what
makes it so appealing as a prison, not just that it keeps it more
likely to stay hidden from the Muggles, but that it also makes it
even harder to magically escape it.
I could be absolutely wrong because one does need to make some assumptions and "read between the lines" so to speak, but the cannon seems to at least not refute the hypothesis, if not support the hypothesis.
