This could be caused by different things, lets go through a few to see if we can narrow it down.
If you only have one email account configured and it is happening with only some on that one email account then I would surmise it is on their side. This can be caused by anti-virus checking emails before sending it out and inadvertently sending it twice.
However, if you have more then one email account then let's review some possibilities.
More then one email address configured on your Outlook. Having multiple email addresses using the same POP3 incoming and same SMTP Outgoing can cause this issue. See here for more information
http://support.microsoft.com/?kbid=284404
Also make sure that you have all of your updates/patches insalled for Office and Windows. You may want to try to remove all email accounts and recreate them.
Kind Regards,