At NewsDemon, we do not currently offer compressed headers which is probably causing the most of your issue.
To my knowledge, only one connection is used to download headers in the client. Someone at Newsbin can probably answer this better than me, but I think the connections are limited to one at a time so the client can better keep the headers organized in a linear fashion so article numbers/message ID's don't get transposed.
A news client asks the server for the article range and gets something like 1000 1120 1220 (total articles, low watermark, high watermark). Low watermark is the lowest article number in the group (oldest article) and high watermark is the newest.