You are supporting international orders? Spend a few hours making a comprehensive address verification system and reuse it everywhere. Over time the effort expended on this task will hopefully become negligible. Maybe that'll happen after you get your first international order.
It's not as if the data aren't freely available. This is the internet, after all (http://en.wikipedia.org/wiki/Address_(geography)#Mailing_add...).
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