Firewall Integration for an ISP

Am having some problem integrating my firewall (Gauntlet 5.5 NT) in a ISP environment. The ISP runs sendmail 8 on a linux box and uses BIND 4.9 also on a linux box. My problem is that anytime I activate the firewall, some mails bounces back with the error message ‘host name lookup failure’ any clue as to where my problem lies?