1. Read the Rejected Email, look for clues, research any codes

2. Make sure recipient has a proper DNS: A records, MX records, SPF, and PTR

Novell NIMS has good tool called mxtrace

3. Test from outside of the network (Yahooo, Gmail)