Thing is, it was working fine before, for weeks, with the same ISP. The only difference is, I had another router BETWEEN my machines and their router, so clearly they cannot be blocking port 25 or my mails wouldn't have been getting out before I pulled the old router off my LAN, either.
If it helps figure things out, I'm using AT&T U-verse.
I was on Clearwire before, and their modem was just a modem (that is, no router on it) with just the one ethernet connector. I have several machines in this room on a LAN, with ONE machine out in another room, connected via a really long ethernet cable. The Clearwire modem was in the same room as most of the machines, but when we switched, the new modem was now in the other room, with that long ethernet cable running from the back of the router here (where the Clearwire modem used to be connected) to a regular ethernet port on the new modem/router there, but I'd left everything in the LAN in this room the same. I placed the issue of there now being two routers into the "I'll deal with it later" pile, since everything still worked: mail still came in and went out, and I could still websurf and whatnot from my PC.
Well, a bit over a week ago, after an unrelated issue with my internet service (the connection quality had suddenly plummeted), I finally decided to pull the old router out of the equation to simplify troubleshooting the other problem, which turned into a headache of its own because the U-verse modem/router is hard-coded to be on the 192.168.1.x range instead of my preferred 192.168.0.x range. Normally that wouldn't have been an issue, since machines on such "adjacent" ranges can see and interact with each other... but SMS Server, as some sort of security feature, is hard coded to only let someone on the SAME range get to its configuration web page, and this security feature apparently cannot be turned off! (Facedesks!!!) So, I had to go in and change the server to now be 192.168.1.5 instead of the 192.168.0.5 that it was before. And of course I had to change things so everything now went out through 192.168.1.254 instead of 192.168.0.1 (which was the address of the old router).
The only thing I can think of is, I maybe missed a configuration tweek somewhere on one of the panes in the SMS Server web interface. That, or the u-verse modem/router does NOT do something my old router DID do related to connecting or directing local machines to the outside world. I DO know the old router had a mechanism in it to hand out local IP addresses to machines on the LAN that needed them, which I don't know if the u-verse router does, but I don't think that has anything to do with my issue.
---addendum:
Going to the Configuration > E-Mail pane and clicking the Change email delivery settings button (but then leaving things untouched), it seems under SMTP Server, I have Address of Internet provider's mail server set to my webspace provider's outgoing email system, on port 587. That is, I have in that field something like joshua-w.mywebprovider.com:587 and I have SMTP Authentication for Internet provider set to Enabled.
Again, everything worked fine before I pulled the second router out of the equation, with the same ISP. Again, pretty much the ONLY change in it's settings that has been made was that SMS Server is now 192.168.1.5 instead of 192.168.0.5, and it is pointed to 192.168.1.254 instead of 192.168.0.1 as the gateway address.