Aha! Was just thinking over the significance of your outgoing mail being a different ISP / domain. I've seen problems several times before in Outlook Express on my customer's PCs (and even at the office using Exchange Server) where incoming mail works OK but outgoing mail doesn't or vice versa. It's almost always down to authentication and, as you've just installed the new high-security SP2, authentication could be where it's now falling over.
The most memorable time that I had a problem with outgoing mail on Exchange Server was when the ISP decided to change the address of their SMTP server and not tell me! Could this have happened to you? You'd never know until you phone them if your ISP is as bad as mine
If you're using standard CAT5 / CAT5e cabling, I can't see that you could set it up so badly that it would have such a poor signal as to keep dropping packets and stop working.
Here's my checklist for this scenario:
1. Is my version of Outlook compatible with XP SP2?
2. Is my firewall compatible with XP SP2?
3. Is the SMTP server address (e.g. smtp.mail.ispname.com) still correct? Do they now have a different server for XP SP2 users?!
4. Have I messed about with the outgoing mail settings for username, secure password authentication, etc? Should I?!
5. Can I connect one of the XP clients to the "dirty" side of the firewall and try it?
6. If I get really stuck, could I uninstall SP2 from one of the clients and try it again?
Let us know if any of those ideas help