We noticed that recent ranges did significantly more IO, and noticed that these ranges were added after the last autovaccum.
After vacuuming the query completed in third the time π
Not the silver bullet we were hoping for, and I still can't explain the diff, but it's a start!