But its Not a Myth, PayPal is covering you when somebody is trying to scam you, so i have Chosen this one for the Safety of Both
The solution is not so hard to figure out:
Use escrow!You send the specified amount of bitcoins to the escrow, the escrow gives the go ahead for the PayPal handler to send the payment, you confirm the payment was made and the escrow releases the funds to the exchanger who originally had PayPal. Done! Easy peasy, no need to fuss about who goes first.
The above method doesn't cover PayPal chargebacks, in case anyone didn't know. Applicable in this case because I'm assuming the OP is only trading with people who he'd trust.