> downloading billions of headers to try and find a
  > particular NZB is a mammoth task

This is true. Even a ~10 of years ago, downloading just the headers on some of the newsgroups shot my cache directory into the gigabytes (for a single newsgroup).