Bluetooth is not consistently implemented by manufacturers, hence you have
two bluetooth devices, your computer and your PDA, that may implement the
bluetooth standard differently.
Pairing any two bluetooth devices involves following different and mutually
incompatible instructions. I have two cars made by different companies that
have bluetooth cellphone connections but require entirely different rituals
to connect the same phone.
I am not sure why you are removing and adding the device or why you would
turn bluetooth on and off on the computer or your PDA. Doing so obviously is
going to corrupt or erase the bluetooth relationships that were previously
established.
I connect devices to my Vista laptop via Bluetooth and once established have
never had to revise the connection (I wish my cars were as stable).
It is more secure, in any event, to connect your PDA to your computer with
the appropriate cable, but that is your choice.