THE SOLUTION

(Technicalish stuff ahead. If you're bored by such things, stop now. You have been warned)

As I said before, there were no more corners I could cut in a conventional way. So I got creative.

What I did was, basically, turn "real" characters into "virtual" ones as soon as they leave the screen. That means every character that is off-screen turns into basic information: a set of essential values in a variable. Their expected motion is precomputed, and they do not move on every frame, but rather "leap" every few milliseconds.

Also, their physics calculations are not handled by the physics engine, but by a "manual" implementation of it that only does checks when needed, and it does so using the most basic data (i.e., if a projectile hits on a certain coordinate, an array containing only off-screen character positions is checked for potential victims in range, then the more complex data is extracted ONLY on those affected).

The downsides to this are very limited. Maybe that character that should hit that rock and circumvent it when off-screen will just blow through it. Maybe those two characters that would've bumped into each other, won't. In all honesty, a player would never even notice or care about it.
All in all, VERY acceptable downsides in exchange for hundreds of extra characters.