I had been pretty sure that the Vrykul were more or less a one-expansion phenomenon, like the Tol'vir or the myriad Pandarian races. I always liked the Vrykul, and in retrospect thought it was cool how they incorporated the Norse myth of the Draugar (Vikings thought that burying a person standing up would cause them to come back from the dead as an evil monster - look down into the big well-like structures under Gjaelerhorn in Howling Fjord and you'll see what I mean) into the larger ranks of the Scourge. (You'll also see a bunch of these in The Elder Scrolls: Skyrim.)
It was the Vrykul who also clued us into the fact that Warcraft's humans can trace their descent directly to the creations of the Titans. In fact, while Dwarves only recently discovered the existence of the Titans in the past couple decades, Vrykul who we didn't kill (or re-kill) in our war with the Scourge would probably remember a time when Titan-worship was their primary religion.
We don't know exactly when the Vrykul put themselves into stasis - places like Utgarde Keep and Jotunheim were abandoned ruins until the Scourge started re-awakening the Vrykul and convincing them that the Lich King was an all-powerful Death God (and don't get me started on the fact that the Lich King was a "death god" with Yogg-Saron, the Old God of Death as his next-door neighbor.)
What we saw of Vrykul culture was twisted, though one gets the impression that the Scourge capitalized on existing culture rather than creating all new ideas (during the Death Knight starting experience, but sadly not after, there's a book you can read in Acherus where Kel'thuzad lays out the Scourge's philosophy - essentially that they don't bother coming up with their own new culture, but instead appropriate that of existing cultures, which is why so much of their architecture has the Nerubians' quasi-Egyptian feel. In fact, all the skulls and "obviously evil" motifs they use are actually practical, intended to intimidate and demoralize their enemies.)
Warrior pride is clearly a big thing, and they have ritualized fights to prove themselves valorous. In Wrath of the Lich King, these battles were officiated by the Val'kyr and determined who got to be the super-powered (and physically intact) Ymirjar, and who would be doomed to a broken existence as a Var'gul drudge.
What we've heard about Stormheim in Legion is that Val'kyr were not some invention of the Scourge. Instead, these beings have been a part of the Vrykul spiritual world long, long before the Scourge ever existed.
The two dungeons in Stormheim will be the Hall of Valor and Helheim. Each of these will apparently explain, or at least feature, two very important Vrykul off-shoots that we saw in Wrath without much explanation.
The Val'kyr are psychopomps - ethereal beings who transport the souls of the dead - much like their real-world Norse myth counterparts, the Valkyries. The Hall of Valor is a pretty direct analogue for Valhalla, the place the Vikings believed those who died gloriously in battle would go after death.
A couple interesting things here. First is that humans in Warcraft don't seem to have any equivalent here. Indeed, human religion in Warcraft is pretty free-form. They believe in the Light, which is a maybe-conscious force of just plain goodness, and that good people will go to the Light when they die, but without much in the way of specifics. The Hall of Valor, I'd guess, is outside of the physical realm, but I wonder if that means it had to be made by the Titans (much like the Emerald Dream and the Elemental Planes.)
On the flipside, there's Helheim, and it's here that we finally seem to get an explanation for what the Kvaldir are. In Norse mythology, Hel (much like the Greek Hades, both the name of the location and Goddess who presides over it,) is somewhat different from the Christian version of Hell, in that it's kind of a neutral place (I suppose equivalent to Limbo.) Of course, given that there was a lot of influence from the spreading Christian religion when a lot of what we know about Norse religion was being written, there was some ambiguity on exactly how bad or not Hel was.
For the Vrykul, it looks like Helheim is definitely the bad kind of afterlife, though unlike the classic fiery cave, Helheim appears that it will be a stormy sea that we'll sail on the Ship of the Dead. And it looks like the wicked, or at least unworthy souls who wind up here are transformed into the Kvaldir.
So not only was Northrend overrun by the Army of the Dead, it was also apparently being assaulted by the Marine Corps of the Damned.
What's interesting is that in Vashj'ir, we discovered that the Naga had recently defeated the local Kvaldir with the help of the Faceless Ones, furthering their successful capture of Neptulon, the Elemental Lord of Water. The Kvaldir served Neptulon.
It's possible that Neptulon had managed to acquire their services somehow, but I actually wonder if perhaps there's a deeper connection there.
The biggest candidates for totally first beings on Azeroth are the Elementals. The timeline I've always found most convincing is that the Titans found Azeroth and locked away the Elemental Lords in the various Elemental Planes (I'd guess that every planet in the Warcraft universe has its own Elemental Lords.) The Titans left, the Old Gods arrived and broke the Elemental Lords out - chaos reigned. The Titans came back, locked up the Elementals again and defeated the Old Gods, locking them up and appearing to be "usurpers" to those civilizations who arose after the Old Gods had come, and thus thought the Old Gods to be the original deities of the planet.
So I wonder, then, if Helheim is not, in fact, its own plane of existence. Rather, it's instead a part of the Abyssal Maw. Those Vrykul who did not prove themselves worthy enough to enter the Halls of Valor (and for now I'm going to set aside the notion that the Halls could be in Skywall) would be cast away, bound to eternal service in the name of the Tidehunter.
Whether this was intended by the Titans or, more likely not, doesn't really need to be answered. But given Neptulon's current status as Azshara's captive, one could see how Helheim would be thrown into disarray now that the Queen of the Naga is making a move.
I really can't wait to find out more about these places.