I think you are running into the following bug which resurfaced at 10.1: NIM081790: When batch geocoding or locating addresses and instersections in the geocoding toolbar and Find tool, an address locator based on the Dual Range locator style does not return matches or candidates when city, state, or zip fields are not mapped.
Try this workaround:
1. In ArcCatalog or the Catalog window, right-click the address locator
2. Click Properties�?�
3. In the Geocoding Options section change 'Match with no zones' from �??no�?� to �??yes�?�
To permanently fix if you are not able to install 10.1sp1 use the following steps.
1. Open the USAddress.lot.xml file located in the c:\program files\arcgis\desktop10.1\locators folder in an XML or text editor.
2. Change the two occurrences of the following tag from false to true.
FROM
false
TO
true
Not sure if this will help you or not:
http://support.esri.com/en/bugs/nimbus/TklNMDgxNzkw
Well, that sure looks like the fix, except that when it says to "Change the two occurrences of the following tag from false to true" there is no "following tag" actually given to change. I assumed it might be the "supportsOptionalZone" property in the XML file, but that didn't seem to work. Guess I can randomly start flipping property flags, re-creating locators, and repeating until something sticks, or bounce this back to ESRI and see if they'd like to fill in the blank on this bug.