Weird issue - pagination returning incorrect record when spanning pages

Hey folks, I appear to have a very weird bug and I can't understand why its happening.

Basically, I have the most simple controller index view which returns bookings which have a status of 1 (active) and then orderby start_date descending and paginate into 'batches' of 20…

      $bookings = Booking::where('status', 1)
      ->orderby('start_date', 'desc')
      ->with(['course'])
      ->paginate(20);

There's a foreach loop in the view, and this just… loops through them all. The pagination links work fine, and its the default paginator, no ajax and nothing custom about it…

  {{ $bookings->links() }}

There's no funky database relationships going on, just a relationship with the course - the booking belongs to the course…

  public function course(){
    return $this->belongsTo(Course::class);
  }

…and the course has many bookings…

    public function bookings(){
      return $this->hasMany(Booking::class);
    }

Now, the problem is this. The last record on page 1 (currently) has an ID of 34. The first record on page 2 (currently) should have an ID of 45. But it doesn't - it shows the details for 34 again; so all the data is from record 34 where I'd expect to see 45.

So, I changed the pagination from 20 to 10. This now means that the last record on page 2 is 34. And that means the first record on page 3 should be 45. But it isn't. Its 34. Again.

Next, I changed pagination from 10 to 21. That means both records should appear on page 1. And they do, only this time correctly - IDs 34 and 45.

It seems that the IDs are only wrong when they span two pages.

Soooo… lets change the pagination to 5. The last record on page 1 is now a different record, with an ID of 56. The first record on page 2 is 30 (which is correct). But its not doing the duplication of record like it is with the others. In fact, if I change pagination to an arbitrary number (7, 8, 16 etc) everything works fine. But when its these two specific records spanning two pages it goes a little… wonky.

What's common between the two records which have a duplication issue? Well, both have a status of 1. They're on the same course ID number which is 29 (however there are other bookings for other courses which span pages and they're fine). They both have the same start date. All the other data is unique (attendees etc).

Does anyone have any idea why this should be happening? It makes no sense to me at all.

Any advice greatly appreciated!