Do you have a Mobile Me account? Or are you using another type of mail service (gmail, hotmail, aol, etc).
If it's an @me account than log into mobileme.com and check if it is going to the sent folder when in safari or whichever browser you use.
If it is in your sent folder than remove your account in Mail and re-add. Hopefully this helps.