If you truely need to have a design that needs that many nodes to be referenced, you need to either have data integrity (Make sure that the nodes have proper titles so they can be found with the AC widget), or instead you need to build your own and more advanced widget.
The AC widget is not build for referencing 10.000's of nodes, if that is your need, you should create your own widget, that allows the users to input more data and thus easier find the address node they need. With CCK you can build your own widget.
Building a widget is in itself no small task, and building one that can handle these needs will not be any easier. There are a bunch of blogs with guides on how to do this, and you can look at the CCK module to see how it does it to get a better understanding.
Update:
I don't know what this Area 1-4 is all about, but my hunch is, that this could be built more clever to avoid this mess, I could be mistaking, but it seems like a flawed design, if a user needs to pick a reference from a list of 10.000's.
One way to deal with this, would be to let the user actually enter the address, and behind the scenes search for it. If it exists create the reference, if not create the node with the info and then create the reference.