What kind of techniques do other folks / commercial games use for allocating OAM entries and dealing with inter-sprite priority? The most straightforward general way I can think of would be to create a binary tree or ordered linked list to keep the sprites (or metasprites) in order, then render everything to in-memory OAM on every frame by traversing the list in order. This seems expensive though, and largely unnecessary -- depending on the type of game, priorities may not change all the time, and it would be more efficient to modify the existing data than to move large blocks around. Is it common for games to only bother keeping track of priorities if the sprites actually overlap?
You could classify games in several categories :
1) Priority doesn't matter (e.g. Mario, Gradius, Tetris, Mega Man, Castlevania, Dragon Warrior, etc, etc...)
2) Priority does matter (Double Dragon, 3D WorldRunner, etc, etc...)
1) Would just display the sprites in any order, but varying through so that all sprites are visible when there is more than 8 they'll flicker but at least they won't disappear completely.
2) There is several ways of doing this. In my own game engine, I start by sorting the objects depending on their Y by bubble sort. I use a stable sort for the MSB and non-stable sort for LSB, so that objects which are close to each other will flicker while objects with are far to each other have their correct priority.
There is also several cases where priority would not matter, but it still would for one particular sprites. Typically if you use sprite #0 hit, you want it to be sprite #0. Then it gets complicated, but there is always a workaround.