We are talking about device discovery here ( as far as blue tooth is concerned ). There are some APIs that allow you to discover other bluetooth devices in close proximity. If you want to discover a device over far distances there is no other option to use but the web. Have a look at this...
Ahhhh.... i think i know what you are trying to do. You need to host a web server and make both the phones talk with this server. Then... make these phones pass some kind of unique key to the server. The server will compare all the unique keys and link two bluetooth addresses together. Then you could make one of the phones a server and other the client and make them communicate. I wonder what quality can be achieved through this method as far as voice packets are concerned since we will be using gprs.
Oh i forgot to mention that. You ll need GPRS internet connectivity and you have to write code that will open sockets that listen in for a connection.