I second @Reeza 's response. I'm currently using SAS Data Quality for this very purpose. Cleaning up, correcting, standardising and matching addresses is a huge job. Any tool that automates these processes is definitely worth considering. Unfortunately it's a separate SAS product with its own licensing cost.
I suggest you check your data using exact matches on unchanged data to start with to get a better idea of how good your data quality is.
... View more