If you're interested in this topic, Andrew Russell recently wrote a blog post and made a video about how they sort sprites in River City Ransom Underground. It's even more complicated because the sprites aren't necessarily simple boxes.
Thanks, this is very interesting! I added it to the article.
The only difference is that bounding boxes are still used for sprites, but he adds a sort of voxel heightmap inside of it to represent occupied volume.
If you imagine this heightmap as a building with multiple floors (e.g. 1st floor, 2nd floor) the algorithm takes the lowest common floor of each of these buildings and performs an intersection test between them and nothing else. This allows the sprites to interact more fluidly inside the bounding boxes! Neat.
http://andrewrussell.net/2016/06/how-2-5d-sorting-works-in-r...
https://www.youtube.com/watch?v=Ssrkq6_6JYU&t=8m48s