1) yes UUID is specific to each device and in order to connect to a device you need to have its UUID. as shown in the Bluetooth chat example by Android SDK
2) depends on the hardware for example chip sets like the HC-06 does saves the last paired device UUID while the HC-05 dose not ...
3) The headsets that Ive tested (Samsung made) Acts as a server. so by initiating a BluetoothSocket with the UUID of the headphone u can connect to it.
4) Yes it is possible to connect to a Bluetooth head set answered in the post : Using the Android RecognizerIntent with a bluetooth headset
Special notes :
Best way to listen to oncoming connections without any wakelocks that I found is by registering the BluetoothDevice.ACTION_ACL_CONNECTED Broadcast and check the name\mac\UUID of each incomming connection.
Thanks to Hoan Nagayu for the help.