Google has brought back the ability to search the news archive this weekend.
Google News representative, Stacie, announced this quietly in a Google News Help thread:
Great news--we've re-enabled archives search! Our team listened to all your feedback you left here in the forum, and was hard at work to bring you an even better archive experience. From all the posts we received, we heard loud and clear how important these archives are to our users. You can now go digging back in time to 2003. Search on :)
The feature went away over time, starting around August 2011 when Google dropped the home page for the Google News archive. The ability to search it completely went offline not too long after.
Now, Google has brought it back via the search tools filter. Here is how to use it:
Oh, today would be the 19th anniversary of the day AltaVista launched, which is why I used them as an example here.
Forum discussion at Google News Help.