Check with the CoA address point REST service first, which will hopefully take care of a large % of geocodes
Do remaining geocodes via ArcGIS Online.
The Mapzen geocoder is built on CoA address points, so the assumption is that if we can't find it in the CoA address service, we won't find it in Mapzen. I guess it's worth double checking...
The plan is to