From that specs it looks like Archived Feeds using <link rel="prev-archive"> are what should be used for most feeds as pagination does not let you reliably reconstruct the whole feed and is meant more for dynamic content like search results. I'll definitely look at implementing archives for all of my feeds even though client support is probably low - can't expect clients to implement this with no feeds having archives.

Nice, good to know. Do you know if many common clients support it?