Here is most likely how it happened.
You were logged into Ebay and or Paypal at some point and were looking at some item on Ebay. Then you decided to do a search for the item on Google or some other shopping search engine to see if the price was good on Ebay.
At this point the account was compromised by some sleazy web site set up primarily to gain data from your browser cache files or active and open secured web page files. This is the same password hack trick that happens when people want to by gold or credits for some game online while their game is active in the background and the browser is open while they buy the credits.
This is a known security problem with IE and various MS operating systems. I believe it is also a problem with other browsers, but just not as common. It is a hard security hole to fix because of one way the secured cached data is accessed by other unsecured websites. The scamming websites are using a modified browser developers tool to access the data, so you will have a hard time stopping it with a firewall or antivirus. Everytime Microsoft fixes it, the scammers manage to modify the tool again and get around the fix. There are also known spyware and viruses that can do the same thing.
Just now, I got a popup from MS about 5 different security fixes they are now applying to XP, and 2 of them involve IE directly. They all allow some kind of remote system access and compromises.