I tried something different few minutes ago as I really was going to freak out...
I completely deleted ALL the music from my iPhone. Everything. Turned "Show all music" off so that the device stops looking stuff up in the cloud and I then ran a full sync out of iTunes.
Now, it's looking perfectly fine again on the phone. But that's of course only a 'solution' in case you have your full set of music in iTunes.
But then I was interested to see what's happening after activating 'Show all music' back again. And the album view stays ordered, so far.
By looking into the 'Title' view, it's different. Now you can see one and the same song twice! The first one is already on the device (the one synced through iTunes earlier), the second does show the cloud icon so it's not downloaded from the cloud yet.
Interestingly, when now looking into the 'Album' view, you can see the songs to be also duplicated within the same album, so it's at least no longer getting split, but the Cloud version of one song is still not being recognized to be exactly the same as already present on the device. Then I noticed that there are still two split albums. So, it really seems Apple is doing strange stuff to their music library. Might be that once they completed that, the final solution would be to delete everything from the phone and from iTunes as well (to also clean that side up) and to download a 'fresh version' from the store then.
Let's see... But one thing is obvious, and that is turingtest2's statement.