There's one quest where you see a Vrykul husband and wife decide to hide their weak runt of a child from king Ymiron, and to flee his influence. This was probably not an isolated incident - many Vrykul fled south with their malformed children, and this was the cradle of humanity. All of this occurred before the Sundering - the figure 15,000 years ago is mentioned. The seven human kingdoms often mentioned today trace their lineage back to Arathor, which was founded during the Troll Wars 2,800 years ago.

I already knew that much. However, this only brings up more mysteries. For example, where are the ancient vrykul ruins from when they settled the EK? What happened to them during that 12,200 year period between the exodus and the Troll Wars? Plus, if this was well before the Sundering, then we should see pockets of... let's say vrykuman civilization in Kalimdor as well. Are we going to see any of those in Cataclysm?

The first we hear of the Arathi, they're a nomadic people. It's reasonable to believe that the vrykul who fled Ymiron never settled down; between the wars of the elves, trolls and Aqir, it's possible it would've been fatal to do so. The known human kingdoms didn't rise for millenia after the fall of the Gurubashi and Amani empires, and specifically until after the Amani lost a major war with elves of Silvermoon. The Arathi tribes were barbarians on the edges of the mighty Amani civilization.

It's also possible they DID create a civilization, but all evidence of it was destroyed when the Well went boom; a lot of real estate was destroyed.

Either way, the western half of old Kalimdor was dominated by the Aqir for a good chunk of that timespan, and probably not very hospitable. Combine that with Ymiron's people living in the east, and it's not very surprising there's not any evidence of humanity on Kalimdor pre-Jaina.

Also, seeing as the trappers in Grizzly Hills seem to have their own distinct culture, and combined with the fact that the Alliance had to specifically seek an alliance (no pun intended) with them, my theory is that the Amberpine humans could be the descendants of vrykul who fled north, into the forest, instead of south.

Also, is the origin of the Kvaldir ever explained? I'm hoping they'll have a presence in Cata (in the sunken city of Vashj'ir and all that)

The Kvaldir seem to be an offshoot of the Vrykul that have established a stronger mystical tie to the sea - witness, for example, how they turn into seaweed when killed. Other than that, there's not much lore about them.

There's a quest that starts from an item that drops from the kvaldir in Hrothgar's Landing that implies that the Kvaldir have plans for raids on the southern lands as well. So I'm guessing we'll see them around in Cataclysm, and probably learn more about them.