Speculating that at least some of this behaviour is related the common ground through the USB cable and having separate power sources, I have built an optical isolator.
This incarnation takes 3V3 - 5V inputs and separates the power sources from each side. There is only an optical signal connection between the sides. The solution utilizes a 6N137 optical isolator. I think in some circuits the amount of drive required may be problematic so version 2 will have a input buffer. The output is inverted so a simple transistor (2N3096) inverter is used to set that right again.
So far so good, no "failure to communicate" issues have been seen with the isolation in place. This particular board was already available from OSHPark thanks to Jason Pepas (http://github.com/pepaslabs) so all I had to do was build it. My version has input output buffering, level conversion and an FTDI USB to UART chip.
Jason was kind enough to publish the gerbers, Kicad model and a PDF of the schematic. He also did a nice write-up on his testing experiences.