>As it turns out, MS supplies the "Outgoing Domain" name in the HELO >command. I'm testing a version now that supplied the primary IP address >of the Mac instead.
This works OK on MS Outlook 98 and I'm sure its OK on MS Express as Digitally Signitures won't work without it so I assume you mean a Macintosh version.
If not did you check that you have the node name set under the Win95 Network control panel as well as the domain name?