>>>>> Sven Joachim wrote:

>> (defadvice gnus-uncompress-range (before narrow-range (ranges) activate)
>>   "Narrow the range if it is unreasonably wide."
>>   (let ((ttl 10000)

[...]

> Does not seem to help much, it seems. :-)  With this advice, Emacs'
> memory footprint grew to 303 MB on accessing be.politics at
> news.motzarella.org, another random example of a group with supposedly
> 30m+ articles.  And fetching 50 headers increased it to 574 MB.

I found the other things to be fixed.  Could you try the patch
(for Gnus v5.11) attached below?  It still might not be complete,
so I set the default value of the new variable

gnus-maximum-newsgroup

to nil so that it might not change the present behavior of Gnus.
Now I have

(setq gnus-maximum-newsgroup 100000)

and Gnus runs smoothly with be.politics and comp.os.linux.misc on
news.motzarella.org (though the value 100000 is too much for those
groups, see a note in the docstring of the variable).