Is the problem that you _can_ resolve a new address B to a location reliably, but, don't know if it's the same address as an existing address A? then it seems straightforward to perform the expensive check for near-matches on only addresses that also resolve to a nearby location, and consider them in order of distance. The simple distance calculation shouldn't be expensive.

Or are you saying that you can't resolve B to a location by itself, and have to resolve it by finding a fuzzy match with some A, but you don't know where A might be? Then you need some cheap heuristic match to compute over all records. What about simply the distribution of characters/digits in every string? easy to compute, small, and easy to compare. Presumably near-matches have nearly the same letters and digits, so might correlate well with actual fuzzy matches.