I've come around to this view, too. Also like names, the best solution is to avoid using them for analysis. Run them through an address geocoding service and store the coordinates next to the address. Use the original address for sending mail or filling out forms, and coordinates for analysis.

Unless cleaning, parsing, and geocoding addresses is one of your core business values, let somebody else do it. It's a lot of work that's never really finished. Find a good service, hand them your garbage addresses, and feel confident they'll do better than you could.