Does this sound like a firewall blocking the domainname?
Your firewall shouldn't be blocking domain names anyway, but it may block IP addresses. You should be using a static IP address (i.e., no DHCP) and some kind of DNS server. If you can't connect using the qualified domain name, but you can connect using the raw IP, then you have a DNS domain problem. Make sure your DNS server is setup correctly.
One tool that might help you a little is nmap, if you've not tried it before.
nmap -p1-65535 10.0.0.4
and it will tell you what ports are open.
If you are using Red Hat, then try looking in /etc/sysconfig/network-scripts/ifcfg-eth0 to find out whether you use DHCP or raw IP.
Try sending an email after restarting the Sendmail. Post the relevant lines from /var/log/maillog so we can see what is going on. Also please post the output from the nmap command.