You're right, decades of experience are also very important (though there are youngsters starting on platforms like the NES or TI graphing calculators doing cool stuff as well).
I'm not sure I agree about toolchains, though. The 6502 is not a very good target for C compilation, pretty much any assembly programmer can code circles around what cc65 produces. So, no offense to you or anyone else that writes C for 8-bit machines, but I don't think any of the new games and programs that really "push the limits" of these machines are written in C. So that leaves modern cross assemblers, which are indeed much more capable than common target/native assemblers of the olden days, but don't exactly afford a quantum leap of productivity either.
Then again, modern emulators are a godsend for debugging.
Official NES mappers allowed up to 1 megabyte of ROM (512kb program ROM, 512kb graphics ROM). I can't really imagine needing more than that for an NES game.
Yes, theoretically you could stick an ARM processor in a cartridge and run most of the game off that, using the PPU as a glorified framebuffer. But many (most?) retroprogrammers are in it largely for the engineering/optimization challenge (or else, why wouldn't you just write a retro-styled PC game), so they draw the line for "cheating" much more strictly than even you have. e.g. some fan translators refusing to expand the ROM size of a game and butchering the translation to fit (Japanese text is much more dense than English), instead of using a larger ROM to fit a better translation. Or some NES homebrew programmers not using mappers at all and working within the constraints of NROM (32kb program rom and 8kb graphics rom). So I wouldn't accuse any of these homebrew programmers of "cheating," because if they were actually guilty of it, those in "the scene" would have called their bluffs long ago.
In Battletoads, Rare went a step further and kept only a single frame for each player loaded in CHR RAM, copying over it for each frame of animation.
As for mappers, the 6502 (along with most other 8-bit CPUs from that era) has 16 address lines, imposing a hard-limit of 64 kilobytes of CPU-side address space. Without bank switching hardware somewhere, there was just no other practical way to access any more program ROM than that. Now, Nintendo could have pulled a PC-Engine/TurboGrafx-16 and embedded a bank switching unit somewhere in the console itself, but hindsight is 20/20.
I don't think fancy algorithms and data structures are common or particularly useful in retrocomputing. I think it's primarily because programs were written back then under strict time and financial constraints, whereas now retroprograms and homebrew are written as hobbies, with the lack of deadlines and abundance of passion that entails.