I work in the address verification field, actually (a company called SmartyStreetsSmartyStreets) -- where we do postal address verification (in the United States).
You'll need a CASS-Certified vendor of address data. These companies' software has been approved by the USPS to append missing information onto an address and return accurate results. One such service is LiveAddressUS Street Address API -- or if you have a list of addresses, there's the SmartylistBulk Address Validation Tool -- which will give you the information you need. Both are free to an extent, but pretty affordable after that.
In ArcGIS, I believe the LiveAddress API can be implemented programmatically. Alternatively, a list of addresses can be exported to a spreadsheet or CSV and uploaded into the list scrubbing service.