Can you give a little more detail as to how your current setup is configured to send mail? Normally, I would expect to see your Exchange server to send the email directly to the recipient's primary MX server (i.e. there shouldn't be a need to use your ISP's server unless you were sending them mail).

May not always be the case... but if you are paying your ISP for some kind of relay/virtual email hosting service, they owe it to you to walk you through getting your server configured correctly. (Especially if *they* are the ones who changed something and broke your setup.)

Yeah, I echo mirrorshades'

If you don't pay for an SMTP/Relay service, then there's a completely different issue. Exchange doesn't need AT&T SMTP service to send mail out, it has its own. So you could configure your mail to be directly sent to and from exchange (as mirrorshades also indicated).

You would need to make sure your MX record for your domain pointed to an A record you have enteref for your Exchange server. You'd also want to make sure rDNS (reverse DNS) goes back to your mail server. Lastly, a TXT entry for SPF would be good, check out the SPF Setup Wizard.

I believe those AT&T changes are really only intended for residential users that use email clients. Unfortunately, no staff at the contact numbers know anything about using their system as a smarthost.

We use an AT&T smart host on a business DSL account with static IP. For our type of service, it was sufficient to just change the name of the smart host in the Exchange SMTP connector to "smtp.att.yahoo.com". Formerly it had "sbcglobal" in the name. SSL is not required.

If SSL was required, you would need additional software or need to stop using the smarthost and send email directly out of Exchange. Exchange does not support SSL connections.

The downside of not using a smarthost is that other mail servers don't really know who you are since your mail server is "small potatos". Therefore, you may be much more likely to make a spam blacklist. Additionally, if your mail server is down for any reason, nothing else holds your mail for delivery until it is back up. A smart host does.

If you cannot seem to get your settings to work in your area, you could also change vendors for which smarthost you use. Although it costs money, an account with some place like ExchangeDefender would provide you with a smarthost that also does all the AV and spam filtering for you.

The downside of not using a smarthost is that other mail servers don't really know who you are since your mail server is "small potatos". Therefore, you may be much more likely to make a spam blacklist.

In my experience, so long as you take the steps to identify your mail server according to the proper conventions, you're in the clear. The main topics to make sure you've done to not be flagged as a spam host are:

1. Valid DNS A and MX records for your mail server. this is done at your nameserver, often the same as your domain host.
2. Valid reverse DNS PTR record for your mail server. This is done by your ISP.
3. Valid SPF TXT record. This is also done at your nameserver, often the same as your domain host.
4. Make sure the fully-qualified domain name for your mail server software is reporting the proper A record and the outbound traffic it sends is using the correct IP. There should be a setting for the fully-qualified domain name somewhere in your email server's software.
5. Make sure your email server is not configured as an open relay. You can use this test here. Do not check the "report open relays" check box when testing your own server. Leave it unchecked.

Although it costs money, an account with some place like ExchangeDefender would provide you with a smarthost that also does all the AV and spam filtering for you.

I agree there is a benefit of purchasing a smarthost account that will provide good AntiVirus and AntiSpam protection, though I often do that on my own and could help direct some frugal administrators to some resources on that.