I've never heard of guaranteed pauzes between the messages, so I would not count on them being there. Sorry. Also, remember that while a new byte comes in through the UART, you can already start processing the previously received one. If you do the math: a byte coming in will take 1/3125th of a second. One (or well, many) 8052 instruction takes only 1/1000000th of a second! So you have more than 300 instruction cycles available to work on the received byte before the next one will have arrived completely. This will also give you an idea of how "un"-heavy MIDI is to process for a 12MHz 8052.
31250 is right. Uh, I was just talking from the top of my head here. Yes. Running status is pitfall number 1, but I see you have it in your sights already. I've seen a lot of newbies stumble over that one.
About processing, it depends on what you want to do of course. But I'd say that receiving and interpreting will take no more than 1 to 5% of all the CPU time you have available, taking into account what I have explained earlier about the byte versus instruction cycle timing. I'll try and dig up the example, and e-mail it to you. The example I have switches a couple of relays in a tube guitar amp according to the program number sent. Supports omni mode, and processes some conitinuous controller messages as well.
Oh, and one important one: where for RS-232 style baud rate generation you are better off with an 11.0952 (or ...hmmmm... what was that exact frequency again? :-) MHz crystal, for MIDI you are better off with a 12 MHz crystal.
Delays are inherent to MIDI communication, but usually not a problem, unless you have a lot of traffic going on on the same cable (all channels in use). Again, a typical MIDI message will take say three bytes, which at 31250 baud is around 1ms. Just put your mind at ease knowing that on 90% of all the hit records you hear, MIDI was used extensively, and nobody ever complains. Seriously professional studio's use several MIDI interfaces working in parallel, each dedicated to one or two synths to minimize delay.