A quick Google search shows that most commercial usenet providers do not have more then 3000 days worth of text retention. (ie, you can get a little more then 8 years worth of history).
So, unless someone out there has terabytes worth of text storage from way back when (which is one reason why Google bought Deja News in the first place), I don't think it will be possible to get all that history.