PayPal is lying or playing dumb and here's why: Ask them if the customer service agents can see the last four or if they have to enter them first before the customer's records come up. They can see the last four right away. Call paypal and ask them which card you have on file, you cannot remember. The agent can give you last four to identify it.
Exactly. I've done this before when services ask me for my full credit card number or expiration date (to verify), and I ask them for the last four digits (to remind me which card I used).
What PayPal did may be bad, but what GoDaddy did (use the last six digits) to verify is even worse.
If you know the last four digits, you have a better than 1% chance of guessing the previous two, since they are not uniformly distributed: http://en.wikipedia.org/wiki/Luhn_algorithm
(There are actually even more restrictions than the Luhn algorithm on credit card numbers, but I won't go into them here. Suffice to say, there's a reason than the attacker says he was able to guess it in a single try - he was lucky, but not that lucky).