This has been a pet peeve of mine for a very long time.

Creating a free-form address parser might be a fun project. Validating the addresses might get expensive though. Are there any low cost/free alternatives to a service like Experian's QAS?