Is parsing the addresses on the back end harder than providing the same number of support formats on the front end?
It's a terrible system really, and the only solution that I've been able to rely upon is having the user parse their own address and supply it to me. At least that way I don't have to spend hours looking through regex statements and edge case detection logic to figure out why a street address was parsed in a particular way.