Well about a year ago my Gmail account was hacked. Nobody had my password, I am not stupid enough to give out my details to any phishing scam, and I have excellent security on my pc. I shut down my pc, went out, came home and found that spam had been sent to everyone of my contacts, after which all of them were deleted out of my contact list. After doing some research I found a few other people who had the same problem, as well as a few yahoo users. After reporting it on the gmail support group along with a handful of other victims, gmail implemented the feature which shows the ip address of the last few logins.
So these accounts have been hacked before, and I was a victim.