Oooooh.. so it has multiple IP's? And it's part of an internal network so you must be using NAT or something. Mine does too. Okay, that gives me some other ideas.
Exchange Administrator --> (Your Domain) --> Administrative Groups --> (Your Netbios domain) --> Servers --> (Your Server's name) --> Protocols --> SMTP --> Default SMTP Virtual Server (or whatever yours might be called).
Right click on "Default SMTP Virtual Server" and choose "Properties".
First page ("General"), what do you see for the IP address? "All unassigned"? Because I'm wondering if, instead, it should be restricted to only the one that connects to your DSL. Like, maybe it's trying to send mail via the wrong IP subnet and not getting anywhere. I've only got one address on my server so I'm not positive if you restrict yours like that that it will help, but I don't see any harm in giving it a try.
I'm a little put off by the NDR message you're getting, "unable to verify address". Tried Google to see what other suggestions there might be and didn't find much except more stuff about DNS. I'm suspicious that there may, indeed, be some type of DNS problem but, to be honest, I'm drawing a blank about what might be wrong.
So, okay, if specifying the IP didn't help, let's try a couple more things.
Go back to "Default SMTP Virtual Server" properties. Notice on the bottom of the general page that here's where you enable SMTP logging. Remember that, might come in handy if all our other attempts continue to fail. Because we can look at the log for the blow-by-blow account of "who said what" and "what was the response" if nothing else works.
Click the "Delivery" tab. Click the "Outbound security" button. On mine, I have "anonymous access" and nothing else enabled on that page. Unless your ISP gave you something specific to put there, how about trying "anonymous"?
Back to the "Delivery" page. "Outbound connections" button. It says to use TCP port 25, right?
Back to the "Delivery" page. Click "Advanced" button. Look at your "Fully qualified domain name". On my server, since it's internal and does not directly deliver messages (it uses a smart host), what you usually see there is your Exchange server's internal DNS name. ie, MyServer.Mydomain.com. However, you might need to change that so that it agrees with your external DNS name. For instance, ours is mail1.mydomain.com. MyServer <> Mail1. (Where <> means "does not equal".) What I'm thinking is: Perhaps your smart host is confused, "Hey, that's not the right name for that server!" Perhaps what's happening is, when your server connects to the smart host, the smart host says "what's your name?" So your server might answer "well, my name is myserver" (ie, the internal name) and when the smart host looks at what server should be at that IP, maybe it sees something like "mail1" instead. So it might be refusing the connection because the names don't match. (However, I believe you would see a different error if that was the case. Like, "connection refused".) So you may need to add your external name to your internal DNS or to your Exchange server's host file so that the external name resolves to your server's internal IP then put that name into the "fully qualified domain name".
Next, since you use a smart host, re-check what's listed in the box under "smart host". Who knows, maybe it's something as simple as a typo. A letter o instead of a zero or something silly. I've also got "attempt direct delivery before sending to smart host". That's enabled even though my Exchange server can NOT deliver external mail itself. I don't remember where but I read that you do that so it doesn't blindly send all your internal messages to the smart host too which, of course, just turns around and sends 'em back since that's the correct final destination. Big ol' waste of time and resources.
Do you have anything in the "masquerade domain"? Mine is blank. However, your ISP might (although it's not likely) have told you to put something in there. If so, go with what they said to do. If not, see what happens if it's blank.
Back to the "Delivery" page. Click the "Configure" button (near the "Configure external DNS servers"). Mine is blank. However, your ISP might have told you to put something there and if so, go with what they said to do.
Okay, let's go take a look at the "Internet Mail Service" connector. Exchange Manager --> (Your domain) --> Administrative Groups --> (Your netbios domain) --> Connectors --> Internet Mail Service. Right click on "Internet mail service" and choose "Properties".
On the "General" page, under "Local bridgeheads", you should see your server's name listed to the left and "Default SMTP Virtual server" (or, if you have multiple virtual SMTP servers, then which ever is the correct SMTP server) on the right. I also have "Use DNS to route to each address space on this connector". If your ISP said to do something different, go with what they said.
Click on the "Delivery Restrictions" tab. I have "by default messages from everyone are - accepted" and there's nothing listed in the "reject messages from".
Click the "Connected Routing Groups" tab. Mine is blank. If your ISP said.. okay, by now you know what I'm gonna say.
Click the "Address Space" tab. I have "SMTP" as the type, * as the address and 1 as the cost. Scope is "entire organization". I don't have a checkmark next to "allow messages to be relayed to these domains".
Click the "Content Restrictions" tab. I have everything checkmarked *except* the box under "allowed sizes".
Click the "Delivery Options" tab. Of all the tabs, this is the one where your ISP would most likely tell you to do something special. Always go with whatever it was they told you. Otherwise, what I've got is "specify when messages are sent" and "always run". Nothing else.
Click the "Advanced" tab. On my server, I have "send HELO instead of EHLO". We did that, however, to fix a specific problem that we had with one company with whom we corresponded heavily. Supposedly their server could handle EHLO and supposedly ours could too.. but nothing helped until we used HELO instead. However, we didn't get the error you're seeing. And it was only with that one company. (Something kept dropping the SMTP session right after EHLO. We even tried it at the command line.) Anyway, just for the giggles and grins, try HELO instead of EHLO.
And that's all I can think of to try, right now.
Each time you make any of the changes above, stop and restart the SMTP service. You don't have to stop all the Exchange services or reboot the server, just the SMTP service. Watch the outbound queue or, if there's nothing there, send a test message. No go? Undo the change and try another. Don't do all the changes at once because, for one, you'll confuse yourself about what all you changed and what used to be there. Plus, if you fix it, you'll never know which change was the right one. So, one change at a time, stop/restart the SMTP service, test it, didn't fix it, put things back like they were and try the next one.
And let us know the results.
(That DNS thing really bothers me.. there's something there. Now, if only I could think what the freak it IS???)