I had the exact same problem, with someone claiming they didn't receive it..
I had to take the hit, refunded him the amount (20 quid.) however the Post Office gave me a form to fill out saying it'd been lost, and they gave me the 20 quid back.
Now with eBay, I only ever sent items recorded delivery.