PayPal seems to have a lax attitude towards security in general. I had a similar issue a year ago, that (fortunately) didn't end up in having my account compromised <http://www.sanspoint.com/archives/2014/09/11/great-paypal-em... but my dealings with PayPal support didn't give me much hope for if and when things do blow up.

In this case, it's likely that phone support is optimized for speed, rather than security. Good if you're legit, bad if you're a target.