I have been using allthenewsgroups.com and newsbin pro. This combination seems to work great with the new beta of newsbin that supports Message-ID's. It looks like some providers are being indexed at http://www.binnews.com
which makes it easy to find the files I am looking for.
As for pricing schemes. Alot of the providers out there are charging for header downloads which is just a waste of your quota. If you can find a provider that does not charge for them, and also supports grabbing articles by message-id's then you are really getting your bang for your buck.
Some of the providers that are out there have the "all-you-can-eat" setup, and this is fine if you are not worried about the quality of service you getting from them. Premium providers like Giganews, Easynews, and Allthenewsgroups offer a priced tier structure because this allows them to provide the highest quality of service to each of their customers.
Lastly, you might want to look at some of the other forums around, because Astraweb and Usenetserver (two of the main unlimited sites), have been having issues for the past few months.