This often better done in data profiling tools like Dataflux.
I have worked on address standardization but mostly through the hand written code. I used to do this on basis of business rules defined by stakeholders(regularly new rules were defined, say once in couple of months), it solved most of our problems but was not enough ( this is what I strongly believe).
When I was in this project they allow me to use Dataflux, because I was told that running Dataflux on large datasets will take lot of time. I was using datasets close to 200 million records and was using explicit SQL pass through.
Below is paper on Dataflux, which you might find interesting
http://www2.sas.com/proceedings/sugi30/102-30.pdf