General :: Mail Server On Amazon Web Services?

We have our web site hosted by Go daddy and they provide us with the mail service as well. But there are a lot of constraints with the mail service with regards to the number of mail boxes, size per box, relays per user and so on.To avoid this, we are looking at other options. One is to have our own mail server but it will require a lot of infrastructure and expertise. But Amazon web services looks nice. They have infrastructure needed and all. One thing on my mind is the reverse look up of the mail servers. They wont be associated with the domain as both would be on different hostings. I am open to both windows exchange server as well as Linux server. Has anyone done this before or has any idea about it? I have gone through some of the threads in their forum and there are a lot of mixed views about it.And main concern everyone views is the reverse lookup. This could lead to all the mails sent from my server tagged as spam at the recipient end.I could not make out in which forum to write and hence in newbie. If this is enough about networking or server please move it.