This happened to me a few months ago. I don't know how they got the password, but it was just one spam message that went out (to like 6 people on my contact list). GMail was 0 help at all in the situation - they wouldn't even tell me the IP that it came from (the IP scrolled off the list they keep because of all the account changes I did following that). There was no evidence of anything at all on my machine (using three or four different scanners).

My brother's guess was that it was a brute force hack and they finally got lucky with it, but of course we can't be sure. I haven't had any problem since then, so it seems to be a one-time deal. If you Google the message that was sent, chances are there are a lot of people out there with the same issue and it hasn't been addressed by Google yet (saying where they got in, from the client itself and it being always logged in, password and another machine or server levels).