Doing this kind of thing was my first introduction to Lagrange interpolation, too, but it turns out that you can do Lagrange interpolation without trial and error; you can just use linear algebra, since the points are a linear function of the coefficients, regardless of the degree of the polynomial.
This was in fact the first decoding algorithm for Reed–Solomon codes, but it's not very efficient when you don't know which of your points are the ones with the corrupted data; you kind of have to guess, which gets expensive fast when you're trying to tolerate more than one or two errors.
Although it turns out that there are better algorithms for that, the most commonly used RS codes don't actually encode a series of points on a polynomial, as subjoriented's comment at the root of this thread suggests; instead they are so-called "BCH codes", where you consider the data you transmit (both the original data and the "parity" symbols) to be actually a sequence of coefficients. So where does the redundancy come from? After all, any set of numbers is valid as the coefficients of a polynomial.
BCH codes require the polynomial to be divisible by a known generator polynomial, and that's where you get the redundancy you need to correct errors. Gorenstein and Zierler published an efficient error-correction ("decoding") algorithm for BCH codes in 1960; the first efficient decoding algorithm for original-view RS codes (where you transmit a series of points) wasn't found until 1986, and even today, BCH-code decoding algorithms are more efficient than original-view decoding algorithms.
The Gorenstein–Zierler algorithm works by evaluating the received polynomial at the roots of the generator polynomial. Since it's supposed to be a multiple of the generator, it should be zero at those roots, as the generator is; if it's nonzero, the values at those roots are due to some "error polynomial" that's been conceptually added to your message in transit. If you suppose that it has only a few nonzero coefficients, there's a clever way to compute the error polynomial from those values that should have been zero. This allows you to subtract it from the received message to correct the errors.
At least, I think that's how it works. I haven't implemented an RS decoder yet, so I might be getting some of this wrong.
But something like that was what I was actually hoping to read at the above link.