I'm also having this issue and would appreciate any suggestions!
I ran into this issue too and ESRI recommended that you store you locators outside of the geodatabase.
Thanks, David. If anyone else is interested, there's some more discussion of this error here: Re: ArcGIS Server in order to Geocode addresses?