Thanks for the hint, Mike!
I did not run yet some data consistency test, to find out which is the limit; so I want to play safe, and most of the articles online suggest to use values that does not go higher than 40k baud.
Since this is UART, I am not aware of how do you actually check for consistency, since it is a much more rudimentary protocol, compared to I2C and SPI I believe.
UART is hardware, not protocol. I2C and SPI are buses. But... I see where you are coming from.
The protocol involved is Bluetooth 2.1EDR. It's pretty robust. The hardware is similarly robust - breaking bytes into bits, transmitting them serially and re-assembling them at the other end.
Be careful of articles that are talking about software serial implementations as opposed to hardware UARTs - the performance and reliability is very different.
On the Teensy3.1, there are three hardware UARTs - use those whenever possible. Obviously you only need to set the rate as high as the traffic you need to transmit (or receive).
If you are looking to find the highest rate the module can do, you will need to factor in a whole range of other stuff - like range, antenna design, voltage, host processor, etc.
The BC-417 module in the 'HC-05'-type bluetooth SPP modules marketed for hobbyist Arduino/maker use can transmit 1.3Mbps on its in-built UART. Bluetooth 2.1EDR can transmit 3Mbps between Bluetooth devices, in theory, but in reality it works out to 2.1Mbps (no relation). The Teensy can, like the Arduino, accept any number as a baud rate and 2Mbps has been achieved with a Mega, reliably. You just need to work out the trade-off between error rate and transmit speed.
And don't confuse error rate with false data - if it errors, it gets retransmitted. When you push the rate so high you introduce lots of errors, your effective baud rate actually goes down due to the retransmits. Also, you need to factor in the devices you are talking to and their maximum rates.
Windows, for example, has a relatively low maximum, completely unrelated to the actual hardware it is running on.