I should have asked this waaay earlier - how are you sharing out your connection? Are you using ICS, or a proxy of some sort?
Here's my guess - many ISP's are very picky on who and who can't access their mail servers, particularly the outgoing mail server. In order to access the outgoing mail server, you usually need to be registered on the ISP's subnet. If you are using a proxy software of sorts, then there is a chance that the ISP can't authenticate the IP address on the client PC. Internet access is fine since it's just flowing through the server, but SMTP for outgoing mail is a little more technical since that machine is making a direct connection to the mail server. If the mail server doesn't like what it sees, it just drops the connection.
That's what I think is going on.
Really the only way that I know around it is to use NAT via router of sorts.