Here's how I solved it. I don't understand why it worked, though.
Firstly, I dumped all the pages into 600DPI png files using ghostscript. Note that in my case document was B&W, so the device chosen in this invocation is reflecting this:
gs -sDEVICE=pnggray -r600 -o pages-%d.png input.pdf
Then converted each single image into a single PDF file using imagemagick. It was actually pretty quick operation, so it wasn't worth to try to parallelize it (with GNU Parallel or similar software).
for file in *.png; do convert "$file" "${file/png/pdf}"; done
Then I concatenated PDF files into a single file using pdftk (other tools would probably also work, but it was what I had already installed):
pdftk pages*.pdf cat output output.pdf
The produced output.pdf file has about the same size as the input one, looks good enough and (what's most important) can be printed by my printer... with the drawback that for whatever reason my printer processes each page for ~5 minutes before printing. I left printing for a night anyway, so I didn't care looking for better option.
So what I did is more-or-less recompressing all the pages.