I need a solution that allows me to create compressed data files (gzip, zip. tar etc. - any format could work) and then freely append data to them without having to load the whole file in memory and re-compress it (seeking while decompressing would be awesome as well). Anyone has a suggestion on .NET?
The reason you basically can't do this the way it's described is that all modern compression algorithms are based on dictionaries that are maintained (added to, removed from) as the compressor moves over the input, and again when it generates the output.
In order to append to a compressed stream (resume compression), you would need the dictionary in the state it had when compression was suspended. Compression algorithms don't persist the dictionary because it would be a waste of space - it's not needed for decompression; it gets built again from the compressed input during the decompression stage.
I would probably split the output in chunks that are compressed separately.