I think this would be an awesome open source project!
Finding the rules and data is but a trivial, slightly time-consuming task. I saw your link before posting my previous comment and took this into consideration: someone reading this immediately has a comprehensive DB of address formats.
"A few hours" may have been a bit ambitious, but over a weekend, and with the required data already available, creating a back-end solution to this is surely not out of the realms of possibility for a reasonably competent programmer?
Have to agree with this being a great idea for an open source project. I had a little look around and the Google Geocoding Web Service (http://code.google.com/apis/maps/documentation/geocoding/) looks like a nice place to start, although most likely outside their ToS. For everyone else, it's determining what's good enough from what's perfect (a good starting point: http://www.endswithsaurus.com/2009/07/lesson-in-address-stor...).
Edited: And the resources on a previous HN posting for this article are helpful, too: http://news.ycombinator.com/item?id=1232042