Many admins on this forum have reported that this is frequently due to reverse DNS lookups not resolving properly or not at all.
Is your exchange server using DNS to send e-mail outbound (this is the default)? If so, does the public IP address for it have a reverse DNS entry somewhere?
You will have to work with your ISP on this, if they haven't delated the zone for the reverse lookup to you.