Why don't my Photos sort correctly by date?
Okay, I solved the mystery.

All of the photos in question were taken when I was on vacation, and my phone's time zone was set to the "away" time zone. Most of the photos were correctly saved with that time zone.

But for some reason, a few photos (the out-of-order ones) were saved with my "home" time zone. These photos also had no GPS location saved, so I assume this is a bug that happens when it can't find your GPS location.

Interestingly, the out-of-order photos did have the correct time, for the "away" time zone. It was just the time zone itself that was off. That's why it wasn't obvious that their time was wrong; Photos doesn't normally display the time zone. The only way to find out is to select "Adjust Date and Time", since that dialog shows you the photo's current time zone.

To fix this, I had to find all the out-of-order photos. Since Photos has no obvious way to filter Smart Albums by time zone, I filtered by "Photo is not tagged with GPS". (EDIT: I ended up writing a script to find them, since this didn't find all the right ones.)

I selected these photos, selected "Adjust Date and Time", entered the "away" time zone, then adjusted the time back to the original. That way it changed the time zone without affecting the actual time.

Afterwards, my photos were sorted correctly.