Just to provide a broad overview, Geocoding processes assume the address data will be fed to it in a certain way. Depending upon what type of address locator one employs (single field or multiple field), the data input to it will need to be in a certain format. So the cleanup process usually involves arranging the data into the needed format. This often involves creating new fields in the input table and then calculating over parts of the original data to come up with the combination(s) the address locator needs so one gets a relevant geocoded result. Or one may have to parse out pieces of data from fields to populate new fields. For example, parsing out "123 Main Street" into a StreetNumber field ("123"), a StreetName field ("Main"), and a StreetType ("Street") field.
Note - if you don't have an address locator available, you can build one. This will take some learning.
In terms of accuracy, that can be a major issue. As Joe Borgione mentioned, a typo where "Maine" is entered instead of "Main" will will probably not produce a match when geocoding. So you may need to do some checking to look for typos, missing data components, data in the wrong sequence (example "Main Street 123" instead of the expected "123 Main Street", etc.
In general, I would say a one-shot perfect geocoding run is not possible outside of a classroom. You can get many of them to work by geocoding in the first try, but there will always be some addresses that will elude the process. Then one has investigate them and maybe correct the data, and do several followup geocoding runs with different settings to finally get them to work. Expect the ones that don't work the first time to take a bit of effort to resolve.
Geocode Addresses—Help | ArcGIS for Desktop
Chris Donohue, GISP
