>Without the flow control the data gets scrambled if you go above about 9600 bps.
That sounds like you have really bad hardware somewhere. You should be able to get vastly more throughput.
>So I want to know the data is clean and not guess about it.
You will never know. You can only bound undetected error probabilities. No checksum, no CRC, no error correction can prove no data loss or bit flips in transmission. This is why understanding channel error types is important to design a protocol that maximizes likelihood of no undetected errors.
I've built many similar sounding systems (even many POV items, I am co-owner of hypnocube.com, and we used to do all sorts of POV experiments, using both COTS hardware and lots of custom boards too). I've found that with even average physical connection we could routinely push 100Mbps into a PC with zero errors over UARTs for literally terabytes of data (I'd create test programs on each end, sender would blast known data patterns and receiver would check them, I'd let them run for days on a test device, looking for errors). This is how I learned a lot about getting good connections - vastly nicer than fighting with flaky hardware connections.
I never needed flow control. Ever.
Have you measured the error rate? Have you looked through forums to see why your Arduino setup is so terribly slow? It sounds like there is a significant other problem than your serial protocol.
If you can use something like a Selae logic probe attached close to your cpu pin out you can also get some good data. I've used these to track down many physical bus errors.