Geocoding has been very problematic for me since installing SP2 and I have two incident numbers going with ESRI now and have posts going here also; not similar to this though.
I have a thought regarding where you are trying to store the locator and whether it has a projected coordinate system. There was a known bug, that was fixed in SP2, regarding composite locators with projected coordinate systems in file geodatabases...
...try creating your locator in a stand alone folder, just to troubleshoot maybe...