I'm not sure I understand what you mean when you say that you "have to restart your server". Is it something like this the following?
- You create/start your EC2 instance
- You try to send an email, but it won't be sent out (if not please show us the content of /var/log/mail.log for that mail in order to see why it wasn't sent)
- You reboot the instance
- Now the same mail is sent out
If not, can you describe the circumstances and your actions and their consequences in more detail, please?