My bet is that the other smtp server is checking you reverse domain as a spam defense and finding that your reverse domain is not delegated to you. Check and fix this with your upstream ip authority.
Len
==============
Anybody have any ideas as to why they'd be showing my domain as invalid? I
can't finds any problems with DNS or elsewhere.
