Isn't Trillium a product that was branded with Oracle at one point?
http://www.oracle.com/technology/products/warehouse/pdf/TrilliumOracleFAQ.pdf
We are using Trillium for much the same purpose (standardizing addresses). As you say, it's been done before, but now they charge a pretty penny to do it for you. You might look into shareware and see what's available.
-- //www.freelists.org/webpage/oracle-l