When you list something for sale, the 'paypal only' accepted payment option is the default. As well as mentioning cash on collection in the free text blurb, you have to swallow this:
We're making transactions safer for eBay members by updating our accepted payments policy. The policy requires all sellers to offer PayPal as a payment method in their listings.
...and tick a little box that allows you to accept other forms of payment in addition to paypal. Likely the seller just overlooked this bit. Easy enough to do, the listing page is pretty busy.
If the seller is stiffing you because it didn't sell for what they were hoping for, there little point in you giving a paypal 'deposit' as that is all you will get back when the seller finds some reason to cancel the sale. You could leave bad feedback i suppose but for low-volume/occasional sellers this is probably still 'worth it' if seller feels like they are missing out on the money they thought their listing should have sold for.