You said the messages are going out, but you didn't mention if the other side is receiving the messages! If they are being received, check the Mail preferences. Under Accounts, select the account and go to Mailbox Behaviors. See if sent messages are being stored.
If messages are not being received, check the SMTP settings for the outgoing server.
You can also open the Activity window or the Connection Doctor to try to figure out what's going on.
Steve