This problem happens when you send email, but not when you receive? Isn't it the authentication needed by smtp?
"Now, I have setup the same email accounts using the root account and they can send and receive messages. I have checked and double-checked the settings and they are identical."
At first, be careful. This is not recommended, as you are logged as root and doing stuff on the internet. Solve the problem and use a normal account.
I'm guessing the root user is using the smtp daemon running locally on your system, and do not need an isp's smtp.
I'm not sure about it, but you can try to figure out if your system is running s smtp daemon.
Also, you need to set your authentication corretly on your email client. Its very easy, and you'll be able to send email.