I just did a deduping project kind of like that
Smaller scale, but the approach that I used was to use our existing contract with mapquest to have them geocode all of the addresses, then I matched them up by latitude/longitude. (We already have custom software to make those requests from mapquest.)
It took, I think, 19 hours to process just over 100,000 addresses, and they successfully geocoded a bit over 98% of them.
Barry probably has a better approach to do the same thing, but this worked for a one-off. (Given the existing contract and mapquest code...)
Cheers,
Ben
