Hey, Grant, I found this write-up as it is the same error that I'm receiving and then realized that you wrote it! This is becoming very frustrating! If you found a work-around let me know. I am now exporting to a shape file instead of a GDB and working fine!
The problem occurs with the latest geocoder on the data disc and does not appear with older geocoders from earlier data discs. If you don't want to use the older geococder, the only workaround I could find is the same as you - export to shapefile.
ESRI told me that they were phasing out the data discs so a fix would not be forthcoming.