Thanks for your question — it made me take a closer look at the recovery process. You're absolutely right, and I appreciate you pointing that out.
Postgres requests history files from the archive, which helps determine whether to wait for the next segment or if the timeline is finished. If Postgres detects that the segment isn't in the archive yet, it simply waits for it to appear. Let me know if I’ve missed anything here.
Then I see no fundamental problem with the parallel archiver =)