Best way to interact arduino and python
I did some work in Java using USB some years ago and I can share some experiences:


Things are not neary as straightforward as using serial.
Your code will probably be platform specific, windows being a bit more weird about handling usb. (unless using something to abstract that away, like PyUSB which wraps libUSB or openUSB, this however does not guarantee platform independency because these libraries also have their weirdnesses).
If you drop down to USB level programming, things can get very messy (again, this can be abstracted away). USB is (at least in my opinion) a complicated protocol, especially for beginners. 


So unless you really need something that only USB can provide, a nice and dandy serial communication will give you much less headaches. Thats why serial did not die until now.

As for debugging why your communication is not reliable I would try several things:


See if your application might send something that is interpreted as a control character
Drop your baud rate to something lower and see if it still loses data. If so, you might overflow the buffer of your receiver (and you would need flow control in this case)
Check your hardware! I've had bad wires or solders on numerous occasions