Greetings!
I worked as an Intern on an Address Verification project for one of the incorporated cities in the greater Los Angeles area. I have a few thoughts to share.
Our project started with the acquisition of multiple lists of known addresses. These lists came from voter rolls, sanitation records and a list purchased from a commercial marketing company.
The lists were merged and used as data in ArcPad running on Compaq PDA's (this was a while ago).
Myself and two other interns walked the city for three months one summer and verified whether or not an address was in our list. The ArcPad application was configured as a form that we could fill out in the field. We had the ability to add address numbers to the list while we were in the field.
All of the address numbers collected in the field were post-processed until a master, GIS shapefile of verified address points existed as the end result. This list was then provided by the GIS team to other city departments (e.g. Fire, Police, Code Enforcement, Planning, etc.).
During the post-processing, many different kinds of issues arose. Parcels are sometimes useful for knowing the situs address, but not always. Bootleg addresses were fairly common, as in un-permitted garage units or businesses sub-letting out the back of their building to another company. The Post Office will deliver whatever they have in their bag to a mailbox if the number matches, so bootleg addresses could spring up and be working for the occupants very quickly with no notice to the City whatsoever. Large, multi-story condo developments could be a nightmare if care was not taken to ensure that multiple, co-incident parcel polygons were not being handled correctly.
If going with ArcGIS as your application, I highly recommend acquiring the book "Designing Geodatabases". It has helped me a lot over the years.
Good luck!
Gregory