It was an E-Bay employee who was being dishonest?
I would HOPE that ebay encrypts all passwords so not even employees can see what the password is so I think I would safely remove that possiblity..

As to how ebay might have detected it first, maybe the person who stole it tried many different combinations or maybe the IP was an IP of a person known for doing this to other accounts (Although I would suspect they would block the IP first..but still remains a possibility). Or maybe they used a known-exploit that hasn't been patched yet.

Another thought, you said they restored your settings before you found out, maybe this person DID change the password but ebay changed it back before you found out about it..

[note] I'm not sure if any of these possibilities were mentioned I didn't have the time to read everything in detail, I skimmed through the posts..