Reverse DNS Scenario

[Sumit Kumar]

Dear All,
I have a mail server hosted in the Amazon ec2 environment. The mails are
being rejected from few servers as the reverse lookup points to amazon
hostname rather than my domain name.

Is it possible to install a dns server on the mail server box and do a
reverse lookup.
Or is there a third party who does the same as amazon is not ready to put in
a reverse lookup.

Regards
Sumit Kumar