Can you see the emails on your Sent folder?
Do those emails contain attachements or just text?
I would check the antivirus program , email account settings, (might require smtp authentication) or the recipient's server settings might be rejecting them.
Can you send to them using another app? e.g. Windows Live Mail?