The game actually reserved each sprite some OAM tiles, for special sprites like Banzai Bills and Big Boos even more.
NMSTL actually checks through every single sprite slot and search so long until it hits a used sprite slot. The optimised version is, of course, using an OAM tile index (and some people did, albeit not released to the patches section).
It also sets the sprite tile size and removes the OAM tile when it's too far offscreen. Of course, it is unoptimised, but it's used to save ROM space since Nintendo had the idea that every sprite can be put into one bank... (They don't.)
Once upon a time I made my own OAM rewrite as well, but I never got around to fixing the original game's bosses and a handful of sprites I didn't personally use, so I never released it. It dynamically allocated spots so that priority could be more easily assigned and every slot could be used efficiently, with the downside of being a bit slow.
There's a lot of inertia with how the original game and custom sprites are written. Every sprite in the game hardcodes whether it will be writing to the upper or lower half of the OAM, and fixing that require editing every single graphics routine. The commonly used NMSTL patch just cleans things up for sprites that use the upper half (ie, most enemies), but doesn't do anything for the lower half. So we have inefficiencies like the block of 0x20 tiles being reserved for so-called cluster sprites when they were used in something like 3 levels in the original game, and mistakes like the spinjump hitspark's lower right tile often being overwritten, all preserved even in modern hacks.
"extended sprites" are things like enemy fireballs, hammers, and other projectiles, along with iirc things like smoke puffs and stars when an enemy is spinjump'd. A lot of things.
The "undocumented sprites" at the very bottom of the list is the area that enemies use for their main graphics. Koopas, goombas, platforms, etc. I don't remember what the other two blocks of undocumented are.
A fast way of organizing sprite priorities is by putting sprites on a linked list, and using a routine to arrange them in the correct order. I don't know how much work that would take getting it to work on SMW because different objects have different drawing routines.
Is there any common sprite drawing routines in SMW, or is every single object different?
Some of the enemy sprites share drawing routines (the single and double tile ones), but the rest are all hardcoded based on the needs of the object.
There are some shared subroutines (again, mostly for enemies) like the one that determines if the object is too far offscreen to draw in the first place, and the one that provides an OAM index to write directly to the OAM mirror (index is 8 bit, and determined by a simple algorithm that depends on the level header).
A linked list proper is right out because SMW stores sprites interleaved in memory. You can extend the concept, with a few wrinkles, to an array of sprite indices or something though.
A bigger issue is that a number of things depend on sprite processing order in a weird way, like the behavior of enemies killed by shells. So you can't just totally willy-nilly change the processing order. But I'm not sure how big of a deal this is to non-speedrunners.
Additionally, sprites can just kill themselves and others without telling anybody and they don't really have to call a routine for it or anything, so you might end up with some kinks regarding sprite spawning/despawning. In particular a sprite that kills itself and the next sprite on the priority list on the same frame should probably work.
Most sprites have separate drawing routines but in practice they mostly just plop a bunch of tiles into the OAM in a nice contiguous block (with a few exceptions that a priority thing would probably want to change anyway). So even though you can't nicely extract a graphics routine from most of them it's not really a huge impediment.
I don't know exactly what you'd want this for in SMW though. Better climbing net sprites? There aren't many priority tricks to be had in SMW and most of the good ones you can do by having one sprite draw its own tiles in priority order. It's not like it's top-down.