I'd look at the data you are matching against: it's a street centerlines feature class, right? What is the edit schedule for it? When you create a locator it takes a snapshot of the data at the time and does some under-the-hood things to it within the .loc. I just have to think that some how a street got deleted or a range got changed since the last build date.
That should just about do it....