What clock (crystal) frequency are you using?

Are you using an old, original 8051, or one of the newer derivatives with the "accelerated" instruction sets?

Although only running at 9600 and not 19200, I have had no problems on a Triscend at 24MHz with four UARTs (none with FIFOs) all running simultaneuosly and without flow control.

What software buffering scheme are you using between the UART and the rest of your software?
I am using ring buffers, as demonstrated in the Keil interrupt-driven serial IO example:
http://www.keil.com/download/docs/intsio.zip.asp
http://www.keil.com/download/docs/intsio2.zip.asp

Although you may well need the ring buffer(s) in XDATA (maybe you could use PDATA?), you can make significant performance improvements by using DATA for the indexes (indices?), etc.
And don't forget 'using' on your ISR.
And boost the serial interrupt priority.