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.
Edited to add:
You could try to build a classifier that can tell when two different strings represent the same address. That's not your ultimate goal, I know. But along the way you might be able to learn a useful intermediate vector representation of the strings that is relevant for determining same/not same. And then use that intermediate representation.
In theory that's what a neural network could do. Inputs are two strings; they share weights/layers that transform to an intermediate rep; then the top of the network learns same/not same.
"Simple as that" but in practice you might find that learning this way takes such a huge network to do well that it's infeasible.
Maybe someone knows an equivalent idea that doesn't need the brute force of deep learning.