I'm not suggesting that I know the answer, but a few questions might help other, more tech savvy foccers to help.
How do you send your e-mail? Is it via something like Outlook Express or Windows Live Mail, or do you use something like webmail, i.e. are your main in-box and out-box resident on your PC or on your e-mail company's server? When you say that occasionally sent messages are showing up in your sent mails folder, where is this folder - on your PC or on the e-mail company's server? Where does your address book "live" - on your PC, on the e-mail company's server, or both?
If your address book lives in more than one place I'd suggest setting up some new "fake" addresses, a different one in each of the separate address books (PC, laptop, phone, e-mail company's server, etc). Then, if one of these new addresses gets spammed you should get a returned mail saying address not found. Then, from which address it is, you'll know which address book the spammers used. This won't completely solve the problem, but will let you know where the problem lies - one of your devices or the e-mail company's server. If, after some time, none of these addresses gets used, you'll know that your whole address list was "stolen" at some point in the past ... though I'm not sure what you can do then.