Okay, some more information and examples:
There are a few minor issues with playlists that have all songs in the same directory. They *usually* play correctly. I found one playlist that plays 1 3 2 4 5 rather than 1 2 3 4 5, but if the songs are all in one directory it's usually okay.
However, if the playlist pulls songs from multiple directories on disk, then the first [up to 10] songs are usually out of order.
A 24 song playlist from various directories comes up in this order when shared via a link:
4,5,6,1,3,2 and then 7,8,9 and so on in the right order. This order is consistent whenever I use the same link.
If I generate another share link, it generates a new order: 5,6,7,8,1,3,4,2,9 and then 10,11,12 as it's supposed to be.
This is a consistent order, even if I restart the Madsonic server.
So, it has something to do with initial disk access.
Does this help ring any bells?