USB-to-Serial showing gibberish at 115200 Baud
After thinking it through and finding a single post which was a little bit in the right direction I figured out it is the only remaining possibility to invert the signal and give it a try. Fortunately FT232RL has option flags in it's EEPROM (programmable with "MProg" by FTDI) to set this:
After this, everything worked on every Baud rate. Don't ask me why, I have no technical explanation for it. I'm looking forward to get an oscilloscope for further investigation. Never saw such a strange problem before.
I tested my USB-to-Serial with a Cisco Switch too and it didn't work without this inversion.