The 24K number I quoted comes from the original H10 code - I haven't looked at RockBox to see how it's architected so it's quite possible that more memory is available for "sidebar" apps while in player mode (versus want I presume is a game mode which basically opens up all th resources).
The H10 core firmware (again, the original stuff) kept a LOT of stuff in RAM all the time. The firmware was in two basic chunks - the core (event handler, database, file system, display driver, usb, audio drivers, codecs, etc) and then the OEM stuff (pretty colors, GUI, fonts, etc).
The amount granted to the core was VERY small in relation to what the OEM was given. Then within the core, most every byte was negotiated for amongst the component groups, and there were (of course) priorities for the groups. For example, it would be hard to think that the database folks could get an extra K away from the codec folks.
Okay... moving past the history lesson.
Database reorg is a tricky... You basically have to shutdown everything else on the player since the UI and audio engine is generally driven from the DB. Then, once you start into it, you're stuck at finishing. Sure, you can make copies of the DB and indices, but that itself takes time, so generally you bite your lip and go for it.
Now filters back in the processing power issue... If you had access to say, 16mb of RAM, then you can be pretty efficient at parsing tags, building indicies, etc. But it will still take longer to do it on the box than in the outside world. The thing you have to balance is how much longer it will take. Each additional minute is time away from making the user happy with the device, and runs a bit more exposure to trashing the database.
There's another angle that could be looked at for RockBox, and that's to manage tracks "live" such that as new tracks are discovered, they're parsed and added to the DB. This is something that was tried on the original H10 in the early days but was abandoned 'cause of the overhead. This is REALLY tricky to deal with 'cause you need to be totally invisible to the rest of the system - i.e., there is ZERO tolerance for skipping audio.
I suspect that RockBox is better suited to give this a shot - 'specially if (when!) they get the COP running. Like I mentioned before, the original core wasn't designed as a real dual processing environment.
You mention the concept of "channeling time" into the effort. Good point, but I'll guarantee that the dev cycle would be shorter in the outside world than in RockBox native.