I recently added USB MIDI to Teensyduino. It requires a AVR chip with native USB, like the one on Teensy. Regular Arduino doesn't have this, unless you try using the 8u2 chip on Uno (which probably doesn't have enough memory, but if you compile for Teensy 1.0 and get a .HEX file under 4k, it might work). If you have a compatible board, you should get latency of 1ms or less, and lots of bandwidth, since it's direct 12 Mbit/sec USB. There's a send_now() function which forces any buffered data USB packet to be immediately made available to the USB host controller. If you don't call send_now() after sending MIDI messages, the packet gets sent within the next 1ms USB frame.
This USB MIDI code is pretty new. A few people have used it with success, and I sent and received a bunch of messages to/from Puredata. If you give it a try, please let me know how it works for you.