Exchange 2007 Not Sending Outbound E-Mail

you are most likely delivering mail over a smarthost
check your send connector in exchange hub transport(org. config)
if you want to use smarthost, then you need the address from the new isp, otherwise deliver mail directly over mx

Our send connector has the * in it, and I checked we are trying to send directly

that's something else, and you can't send any mail at all?
or some mail?

No mail ever makes it through it sits for the default 2 days and then kicks back the message that it was not sent.  We also know that our ISP is not blocking port 25.

1 what does the NDR report say when you get it back? (please post it here)
2 what do you see in the mailqueu when you send mail

I tried to find an old message from exchange but I can't.  When the messages are in the queue it always says last error 451 4.4.0 DNS query failed or "421 4.2.1 Unable to connect."Attempted failover to alternate host, but that did not succeed. Either there are no alternate hosts, or delivery failed to alternate hosts.

did you change the gateway on the exchange server???

from the exchange try to telnet to an open relay server on port 25 and see if that works?

The gateway was changed on the exchange and domain controller, and if I telnet to google or RCN's mail servers it does connect on port 25.

and you are sure the exchange uses the dc as dns?and nothing else?

The NSlookup results are fine and I am sure that the exchange server is using the dc for DNS, quick question though where should our ISP's DNS server addresses be put in the dc.  Right now they are in the forwarders where our other ISP's servers were.

you can put them in forwarders, but also as root hints

it seems to me someone has been messing around with iis or the VD's
check this:
https://www.experts-exchange.com/questions/26905239/OWA-2010-Issue-Network-Connection-is-Unavailable.html

i'm sorry , my last comment was not meant for this

At this point I hope you were able to resolve the issue, any update?

No, we have still been working on the problem.  We had our new service provider add pointer records on their servers.  We at the moment have been able to keep up and running by using our old service provider which everything seems to work fine if we use them.  But our time is running out, we will be losing their service at the end of June.  I can't find a single thing wrong with our setup, however I know it still is not working right.

Just to make sure I got everything right, here is what I did when we changed our ISP.

Went to the company who our domain is registered through and changed the MX record to point to our new IP address.

Then had our new ISP add a PTR record for our mail server

changed our file, exchange and barracuda firewall's gateway to the new routers IP address

I know that our ISP is not blocking port 25 and our new router NAT is setup correctly and allowing the right ports in and out.  And our send connector has the * in it.  We started getting mail incoming in about 5 hours and for a day and a half after that, no mail was being sent out.  Then queue keeps saying that the destination mail server does not allow relay or that we are being blocked by the mail server.  When I called our ISP the guy said that the PTR record is need so that the mail servers can be sure that the email came from our server.  Do these steps sound correct and should we be able to send outgoing mail.

nudge..

All of these things put together got us to the answer we were looking for, in the end it turns out that our ISP required us to send mail through their smarthost and would not let us send mail directly.  They claim this is to help reduce spam coming from their customers.