LA County maintains customized geocoding rules (actually the ESRI locator was developed by an LA County contractor many years ago, so our rules fit very well). This has helped up maintain geocoding rates about 99.6% of all addresses.
With ArcGIS 10, ESRI has developed a new set of geocoders and rule systems. I took my first look at it last night – and I am very interested in what they are providing. I think it might make things easier. Especially since it has a single-line geocoder (like Google and Bing) built in. I got that working right away!
For those of you who feel the desire to delve deeply into geocoding (I guess I’m one of them), I have attached the ESRI document that discusses customizing them.
Reference document: Customizing Locators in ArcGIS 10.pdf

