Use an algorithm guessing proggy to generate a working password .
watching too many films where someone cracks into the pentagon system in a matter of seconds?
Not a laughing a matter though, am sorry to hear of your probs.
Like you say there are millions of email users, therfore millions of passwords, involving numbers and letters...
Not saying this happened to you, but many pople get caught out by the phishing emails, where it looks like a website, smells like a website, but just isn't.
From a programmers point of view, its much much easier, in fact ANYONE can copy a login webpage - say ebay's login - then sends out a load of emails with a link asking you to login to reply to a message and the like, you go to the false page, where it logs your details, then fwds you on to the real site...you wouldn't even know.
Easiest way is always type your password in wrong for the first attempt on any site and have a different password for mail,ebay,paypal e.t.c so if it does get stolen, you're not going to lose everything.
Have a feeling that some investigation was done recently and it turned out the majority of this was being done by russian mafia...?
As a parting note, paypal is still one of the safest forms of payment using the internet and is far better than giving your card details, its not perfect, but look how many people use card scanners in shops and petrol stations nowadays to steal your card details...