This is a common problem and one frauds use all the time - they know they have you by the balls with PayPal always on their side. I have seen forums where people discuss the ways they can get products for free by claiming the item is faulty or not wanted, claiming to send it back, and then using PayPal to do their dirty work - they know that most e-commerce relying on PayPal would rather swallow their losses than risk losing such a payment method entirely.
You really should make sure you have a statement in your terms and conditions/return policy requiring registered or recorded returns, this way they have to provide evidence that they did return the item to you. Point out that this is for their protection as well as yours, and that you cannot be held responsible for items lost in the mail process by those who do not return them with proof or sending.
As it stands you have two options, try to fight this with PayPal (who will probably say the same thing I have said and find in favour of the customer) or swallow the cost and treat it like a learning experience, and update your terms and conditions today.