I've always resented that moment every year when I write my check to Lexis/Nexis. Like MediaMap online, it's expensive, clunky to use, and usually isn't nearly as effective as just looking something up on your own.
Google has quietly launched (or so it seems to me) their News Archive search offering. This allows you to search all the way back through 2005... ok, not perfect, but its a start, and every year will only get better of course.
Just go to www.news.google.com and you'll see "google archive" listed below the search bar. Enjoy!!