It sounds like a good idea with the multiplexer, but as you write, it may not be that feasible.
The best would probably be additional UARTs, as you mention.
For my project a solution could perhaps be to pre-program another ATmega microcontroller (with its own UART) to handle the communications with the external device. The device I need to attach is not providing a lot of data that the Arduino needs to process. Rather it's more of a controller. But it requires 19200 baud, nonetheless.
That ATmega could then be connected to some of the I/O pins of the Arduino and the two microcontrollers could communicate with each other, perhaps using the SoftwareSerial protocol (provided that the additional ATmega is also loaded with the Arduino bootloader). Perhaps I2C would be even simpler, as the the data bandwidth needed between the two ATmegas is fairly limited.
All that could be made on a prototype shield, I guess. And then you have the goodness of being able to develop your app for the other ATmega through an Arduino board.
...Or one could purchase a Wiring board and get an ATmega128 with two UARTS - but then you'd need a Bluetooth dongle :
I think I'll go for the extra ATmega168 and the I2C protocol, actually.