Going at this as a thought problem (I have some similar issues to worry about with wanting to add a MIDI merge to my own project):
Since the ATmega doesn't, as you point out, support multi-threading, there is no capacity on the chip proper to buffer one signal while passing another. Which means any function that evaluates a sensor, or sends a serial message, will be executed completely before the chip will "look" at the next function. On the surface of it, no interleaving of individual MIDI messages occurs.
Since a noteOn event take just three bytes to send, and each CC message is three bytes, on the surface of it the interruption to a continuously changing CC controller would be at most a couple of messages. Since the MIDI spec is absolute position, and the ATmega's analog inputs similarly absolute, the controller would in effect "jump" 2 positions out of 128.
In most of the MIDI sequencers I've used, CC data is thinned to 1/4 to 1/10 anyhow. So this doesn't seem musically fatal.
Looking at it from a different angle; would it be possible for a key press to happen so quickly the Arduino didn't recognize it? MIDI baud rate is 31250. Arduino runs at 16mHtz. How efficient are the instructions? Assume one program statement requires, say, 10 steps in Assembly. Assume four different subroutines paging each sensor, and four subroutines for MIDI output, each with ten program steps. Multiply again by the number of sensors (aka the cycles used to sort to the specific sensor or state). That's 15200 machine cycles.
16 x 10^6 / 1.5 x 10^4 = 1,066 pages of each button each second. But that also is the maximum number of complete MIDI messages the Arduino is capable of sending. Assuming 31250 is measuring the 8-bit bytes per second, and the standard MIDI message is three bytes, a maximum of 10,416 MIDI messages can be sent in that same second. So on the surface of it the Arduino, running full-out, is in no danger of creating congestion.
(I would definitely script my CC's so they were only sent when there was a change of state. It IS possible to overload MIDI receivers!)
For yet another angle, let me look at it as a keyboard player. Assume I am playing "Bumble Boogie..." no, better yet, that I play a gliss down the length of my 61-key controller. Assume 1/4 second for 61 note on and note off events. That's a rate of 488 MIDI events per second. Okay, what about a 32d-note trill at 120 BPM? That's a mere 16 events per second? (Did I misplace a decimal?) In any case, we'd have to play five hundred notes in a second to risk losing one due to an ill-timed function call on the Arduino.
So I suspect my math here, but it looks like there are no inherent timing issues. (It is, however, in danger of falling behind if used in a MIDI-merge application. External buffering seems required for my project).