A good ecc algorithm for random errors?
First, it is not true that an error in the parity portion of a Reed-Solomon code word renders the word useless.  RS codes can correct errors in their parity and their data.

Having said that, 10% errors is very high and I would not use a RS code in that situation.  In fact, in a situation with that many errors you will occasionally have > 50% errors just due to random distribution (random distribution is often "clumpy") of the errors.  No code you use will correct all of the errors all of the time.  Your system should be designed with that fact in mind.

I would use a big turbo code or LDPC code.  Either one will get you near optimal performance.  The code needs to be "big" in the sense of using large blocks to avoid the clumpiness problem noted above.  You will still get more errors on occasion, but (assuming a gaussian distribution) your tails will be MUCH smaller if you make your blocks large.

If your errors are bursty you can use interleaving to spread them out among multiple blocks.  If they aren't bursty, interleaving won't help any.