selecting a referenced node from 1000's of nodes I've a cck field "address" of node type Address within Building node type.
My site may have tons of such addresses. So let me assume that already 10000 nodes of type Address exist and then one visitor tries to create a node of Building.

In the node reference field of address how'd one be able to select the correct address from 10000 addresses from "auto complete text field" address field?

As far as I know auto complete address would show only the node titles and  many addresses can have same titles so how one would be able to select a particular address in the address auto complete text field ?
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.