A few points, it's a hard problem, google has put a lot of effort into solving some of it, and it may not be fixable completely.
To start off with, usenet is ancient, much older than the web. Second, archives have never been ubiquitous, expecially in earlier eras. The storage media, e.g. tape, were troublesome and expensive, so most people didn't care. The records we do have back then are from a small number of individual archives (e.g. Henry Spencer's). It wasn't until much later that deja news starting archiving usenet routinely, and even then there can be gaps due to failed delivery. Also, it's possible for individuals to opt out of archiving by setting the x-noarchive header or by contacting google. The result is a swiss cheese record that won't get better unless we magically find new archives and/or decide to violate people's privacy.
It is odd because I feel like I have gone looking for older pre-1999 posts that used to exist in Google and they are no longer there. I had just assumed that support for pre-2000 was dropped.
To start off with, usenet is ancient, much older than the web. Second, archives have never been ubiquitous, expecially in earlier eras. The storage media, e.g. tape, were troublesome and expensive, so most people didn't care. The records we do have back then are from a small number of individual archives (e.g. Henry Spencer's). It wasn't until much later that deja news starting archiving usenet routinely, and even then there can be gaps due to failed delivery. Also, it's possible for individuals to opt out of archiving by setting the x-noarchive header or by contacting google. The result is a swiss cheese record that won't get better unless we magically find new archives and/or decide to violate people's privacy.