I thought the Lost Lands were to the south? And i believe it is mentioned that the south of the Thurian continent has "reptile-reeking jungle", where the pre-human civilization is. So I figured the Lost Lands were where the jungles were. That said, i find your ideas extremely interesting.
Hey Gozer! The location of the Lost Lands isn't given in the texts, nor are they equated with jungles.
Jungles are mentioned as being in "the south" and I certainly believe that there were such FAR to the south on the Thurian continent in Kull's time. Stories like "QotBC" make it a certainty, IMO, and other yarns seem to imply it. Not trying to derail this thread, but I think it just as likely that Kull encountered jungles on the Nameless Continent.
I put the Lost Lands where I did because it was about the only place to do so, IMO. World's End is east of the Seven Empires. The "pre-human South" is directly south of such. Unless "Lost Lands" is a synonym for one of those two (and there doesn't seem to be evidence for that), then those lands must be somewhere else, but close enough where the Thurians would refer to them in casual speech (ie, not on the other side of the world). That left the expanses south-west of the Empires. The fact that HPL seems to have centered his "Lomarean Age" kingdoms in the general area of the Middle East was a factor I considered after I made the previous deductions. Of course, my reasoning can be argued with, but I stand by it.

I love megafauna as much as the next dude, but REH definitely kept such to the fringes in the Thurian AND Hyborian Ages. Please point out anything I missed. Personally, I'd like to think that Thurian Age "horses" were actually chalicotheres (like in May's "Pliocene" books), but there's no evidence of that. AFAIK, not one sabre-tooth appears onstage in the Kull yarns.
I'd like to squeeze in all the megafauna possible during the Thurian Age (I think the Nameless Continent/proto-Central/South America is ripe for such, as is Atlantis itself), but REH mentions mammoths ONCE in a fragment and nothing else of note in any other tales.
My two tals. 
I sort of deduced the existence of Thurian era sabertooths. In the Hyborian Age, there is at least one living sabertoothed cat still alive in Conan's day. The Pictish Wilderness was supposed to be the last bit of untouched wilderness in the West, a remnant of the sort of conditions that existed before the Hyborians came south. So we can safely assume that there were more sabertooths in the past, after the Great Cataclysm. In "Beyond the Black River", when the sabertooth first appears, it is mentioned that no Hyborian hunter has seen one in centuries. This implies that Hyborian hunters DID see this beasts, just not in the present day.
So there were sabertooths after the Great Cataclysm, which means they must've existed BEFORE the Great Cataclysm. I think that after Thurian civilization disappeared, the sabertooth population made a comeback. They would've existed in the deep wildernesses in Kull's time, but rapidly expanded to fill in the gap when the human population took a nosedive. I'm not saying that they were a completely mundane animal in Kull's time; they would definitely be something that existed beyond the edges of Thurian civilization. Keep in mind that the great Thurian civilizations made up only a small piece of the world, and apart from them, only the Non-Thurians of the East and the pre-humans of the South are mentioned, which implies to me that there was a LOT of wilderness.
I have no doubt that there were sabertooths
somewhere on the Thurian continent in Kull's day. I simply stated that REH never mentions them (Atlantean "tigers" might be an exception). I totally agree with what biologists would call your "outbreak" theory. Such was seen here in North America after the massive die-off of the native human population once European diseases were introduced. Populations of wildlife like the bison and the carrier pigeons exploded.
You see the same thing in REH's "The Garden of Fear" and "The Valley of the Worm". In "TGoF" (which by Howard's own testimony is immediately post-Hyborian Age), you see mammoth herds wandering what is probably Zamora or Koth within (maybe) a century of the Hyrkanian retreat. The same thing seems to have happened after the Great Cataclysm.
There WAS a lot of wilderness in the Thurian Age. REH said so in "THA".