Multiplexing means the job has to be done for each scanline instead of for each frame, but each scanline contains less information so the total amount of work to do should be about the same.
not really
let us figure a simple color system. you unblank 0.5, 1, 2 and 4 ms to get 16 colors, then for overall intensity, you go, say, 16 steps, so now the smallest unblank is ~ 30 us. then you multiplex by, say 8 and get an unblank resolution of 4us which gives you a maximum tolerance on your unblank of ~ 100ns. Abandon the multiplesing and your tolerance is 900ns which is a heck of a lot easier to achieve. now go for 256 or even just 64 colors and see how your timing get to be uncontrollable within "invisible" tolerances when you multiplex.

Note, the above apply to signs where it is not every dot same color.

I did, once, do some 'analysis' of making a sign that was multiplexed by a fpga invisible to the uc, that came out as "possible, but not desirable"

OK as I posted in a previous thread, somewhere, if you drop the intensity regulation (i.e. make an indoor sign for an always equally lit location) things get a lot simpler.

Erik