Grrrr.. PayPal... While I haven't had a bad experience with them yet, it's really only a matter of time.
If you use PayPal a lot, you can improve things a little by using the Security Key.. It's a keychain dongle that's $5 (last I checked). Press a button and it'll spit out numbers that PP will check to see if you're really you (or someone who has both your password and dongle). Combine this with a strong password and you'll be in a good position. The technology behind this is good stuff, unfortunately it's PayPal we're talking about so.... results may vary. (PayPal -> Security Centre -> Online Safety Essentials -> Security Tools -> Security Key)
Unfortunately, PayPal has had a history of being rather stupid about security. Password resets, and any number of things aren't handled smartly. Once the dongle is activated, do yourself a favour and go through the process of "forgetting" your dongle at home/office/wherever - You'll find out what info PayPal wants so you can put your own memorable false info in there.
We really need more competition in this space. Google Checkout exists but it's nowhere near as common to find. Doesn't help that eBay and PayPal are tied so close together. Oh, and even more off topic, but related to security, check out the Security Now! podcast (grc.com) if you want to know how all this stuff works. It's a very informative show.