The best way to understand it is that sprite-to-sprite priority (which depends on the sprite's index) is always completely evaluated before sprite-to-BG priority (which depends on the sprite's priority bits in OAM).
Say you have an opaque pixel from sprite 0 with priority 0, from sprite 1 with priority 3, and from a background tile all overlapping at the same screen position. Sprite 0 takes priority over sprite 1 because it is a lower-numbered sprite. Then, the background takes priority over Sprite 0 because that sprite is priority 0. The pixel color that gets outputted at that position is the background tile pixel.
The fact that Sprite 1 has priority over the background is irrelevant because Sprite 1 has already been masked by Sprite 0 before sprite-to-background priority is evaluated.
Many games on the NES and especially on the SNES take advantage of this quirk to selectively mask out parts of sprites and to simulate finer-grained levels of priority than the hardware natively provides.
Ok. In other words, it means that it's "topmost" in each pixel and not in each line. that makes sense and for sure it fixes the new problem in the screen I posted above.
I thought I had already tried to implement the priorities in the way you described, without properly fixing all the problems... but probably that was due to some different mistake of mine. I'll go back and try it again now that I know it is the correct approach.
Thanks a lot for clearing out the matter!