I found this Geocoding Blog entry that talks about ramping up the performance of address locators.
http://blogs.esri.com/dev/blogs/geocoding/archive/2011/02/09/tuning-a-locator-for-improved-performan...
I'm working towards this. I'll touch base again with the results.