In World of Warcraft Legends Vol 3, it was shown that the Nerubians can burrow underneath entire towns in order to topple them, it's not unreasonable for us to assume at any level that these tunnels were freshly made, or were there to begin with.

As well as Kul Tiras, which had damn well better play a significant role in any water-based expedition.

Regarding the Maelstrom realm, in the list of internal Blizzard servers leaked by using the transfer mechanism creativly (I wonder if that still works ?) last year, there were already several realms (3) named with Maelstrom, as you can read back here:
World of Warcraft Server List

So it still could only be a hitch there, but considering Blizzard will have to restrict free traveling with the release of the next expansion again due to the same reasons as given for Wotlk, it would be exceedingly lame as if you just couldn't fly again, this time. But if the next expansion is more water-centered there are a lot of options that do the same but don't sound outright like cold-weather flying MK2. So I personally consider Maelstrom a quite likely theme for the next expansion. Still guesswork though perhaps until Blizzcon. Just wanted to throw in that the Maelstrom showed up long ago in the internal realm list.

Also of note, there were already many "Coliseum realms".

From the 'master plan' that's been knocking around a while and has so far been mostly accurate:

I see two routes they can take with this. Either they can put all the islands close together, and have us fly/take a boat between them, or separate them by long distances and effectively put each in its own 'instance' (i.e., you get a loading screen between islands), surrounded by fatigue waters.

So, how badass would it be if we "redeemed" Anub'arak instead of killing him? Some crazy Ashbringer release-you-from-your-bonds type stuff.

Also, I'm calling it right now; in the Icecrown patch we will get an IQD-style Azjol-Nerub zone which leads us into Icecrown.

Well, we actually win most of the fights in Icecrown because we work with the Ebon Blade, not the Argent Crusade. Argent Crusade just gets us onto the glacier. Most of the rest of the progression quests come from either the death knight attaches or from the Shadow Vault. And these guys *do* have clever ideas. That's even a difference in the writing. Argent Crusade quests tend to be more tactical military in nature. Ebon Blade quests are almost always some sort of strategic headshot.

The Ebon Blade isn't really so much a case of "good guys > bad guys." They're written as extremely powerful bad guys that know how the Scourge work inside and out. There's at least some reason why they win as much as they do. Pretty much alone among the factions you do work for in WoW, it actually seems like these guys can pull their own weight.

If anything, they're due for a loss because they haven't had one as good guys or bad guys since Light's Hope.

I'm getting a "Kerrigan helps Raynor and Fenix in Broodwar" vibe from the Knights of the Ebon Blade and Darion, seeing as how blizzard has dropped hints that Arthas may die, but the Lich King will live-on. Hail to the King, anyone?

I'd imagine we would see Kul Tiras and all the surrounding islands added in along with the known islands around the Maelstrom.

I've said it before and I'll say it again, that 'list' has NO source except for a post that was made on Allakhazam a month after WotLK was announced. Now the Maelstrom is likely next but anyone who has been paying attention to what Blizzard has said since 05 (that they were dedicated to making expansions of Northrend and the Maelstrom) could make a reasonable guess that the Maelstrom was next when they announced Northrend. Also for a 'original' list it is missing Azjol-Nerub which was actually marked as a leveling zone until October of that year.

While that particular list was copied from a recent forum post, I personally saw a similar list also extending up to lvl100 during Burning Crusade's beta, and at least some of that list is unchanged. It is certainly older than last year. At the least, Blizzard stated at Blizzcon last year that Outland and Northrend were originally planned to be in at release, so it would make sense for them to have a general plan mapped out.

While that list has been making its rounds for sometime, just don't put if off yet. (It still remains semi useful)
There was another post back in September 2008 that detailed alot of Maelstrom, but as of right now there is no proof for its accuracy.
But here is the link if you wish to read it: The Next Expansion's Details.. The Depths of the Dark Tide - Unofficial World of Warcraft Forums

That could easily be a hoax, but it's also very possible. Especially with how Arch-druids may be much more viable of an idea given what we've recently learned. At the same time, it seems inconceivable that they would release another melee class, one which has had most of it's abilities eaten up by other classes, and balancing two new classes in one expansion sounds like a total nightmare. Some of the ideas for the zones and the overall plot of the expansion sounds very Blizzard, though, I could definitely see them making those sorts of things, so if it is a hoax this guy is at least a pretty good faker.