Question : Email/DNS issues

My Web Host company controls the DNS for my domain

I have 2 MX Records - the primary one points to my in-house mail server, and the other points to their mail server (as a backup).

Strange DNS issues are happening...

1. If someone sends us an email from *hotmail.com* or *msn.com*, their email goes to my Web Hosts mail server (the one we have programmed (MX Record) as our 'secondary' mail server).

It's as if hotmail and msn think my primary mail server is down (which it's not) and reroutes the message to the backup mail server (my Web Hosts mail server)

2. If someone sends us an email from *att.net* or *bellsouth.net*, their email comes directly to OUR mail server (as it SHOULD, because that is the primary MX record!)

3. If someone sends us an email from gmail.com, the message gets 'lost' ... we never get it. A day or so later, the sender gets an automated email stating:

**********
  Subject Delivery Status Notification (Delay)
  This is an automatically generated Delivery Status Notification
  THIS IS A WARNING MESSAGE ONLY.
  YOU DO NOT NEED TO RESEND YOUR MESSAGE.

  Delivery to the following recipient has been delayed:
         [email protected]

  Message will be retried for 2 more day(s)

  Technical details of temporary failure:
  Unspecified Error (SENT_EHLO): Resource temporarily unavailable
**********

(the email address they are sending to is valid, by the way)



Are there any tools I can use to troubleshoot?

We registered our domain through Network Solutions and I verified that the domain uses my Web Hosting Company's servers for DNS:
  NS1.DISCOUNTASP.NET
  NS2.DISCOUNTASP.NET
  NS3.DISCOUNTASP.NET


My Web Host says (in so many words) "Sorry, we can't help you"

But from everything I described above, it SMELLS LIKE a DNS issue.
What do you think?

And if my Web Host controls my DNS, then really THEY are the only ones that can fix it, right?

I verified that all of my DNS settings are correct. This just started happening about 3 days ago but it is annoying.

I can live with the fact that some of my email gets rerouted to my backup mail server (because I use a third-party program that checks that server every once in a while to see if there are any messages on it, and if there are, it downloads them and forwards them to my primary (in-house) mail server)

However, SOME email just never gets to us and that is what bothers me most.

I have not made any changes to DNS, or my in-house mail server.
And like I said, SOME mail comes to us just fine!

There are three things going on here:
1. Some emails come to us just fine
2. Some emails go to our secondary mail server but nevertheless I still get them
3. Some emails don't get to us at all

(they are not in my junk mail folder, I already checked)

I need some guidance as to how to start troubleshooting, and am I wrong to point blame to my web hosting company, since they manage my DNS? Or is this not a DNS issue?

(Also btw ... I checked with mxtools.com and I am not blacklisted)

Answer : Email/DNS issues

Problem solved.
Turns out it had NOTHING to do with my ISP or my Firewall or DNS.

We deployed a web-filtering product called Untangle.
It's an opensource program that allows me to block specific websites, ports, services, etc.
(For example, block 'myspace.com' from employees)

Apparently there was an update to the Untangle definitions which caused this whole mess. (There's lots of talk about it on the untangle forum)

In any case the issue was resolved and now everything works again.
Thanks to all for your help, though ... it was very informative!