Microsoft Exchange Reverse DNS Failed

We are running a Microsoft Exchange 6.5 on Windows SERVER 2003 SBS. After running the test here

http://mxtoolbox.com/diagnostic.aspx?HOST=mail.arcelectronics.com

it shows
Rev DNS Check:         Reverse DNS FAILED! This is a problem.

I've tried contacting my host and then response I got from them

"Dear Valued Customer,

Reverse DNS is pretty simple and the errors reported here are odd. Basically whatever hostname you are claiming during your HELO should match what the PTR record for that IP is. In other words, please set your mail exchange server name to mail.arcelectronics.com."


it seems that you use your own mail server,
mail.arcelectronics.com 69.15.175.69
and it seems it works fine, mail.arcelectronics.com is already pointing to 69.15.175.69"


Yet the reverse DNS error still shows up and to my knowledge this is forcing some of the hosts to reject our e-mails. Please assist me with an advice.