Try using MacTCP Watcher (or something similar) to do a traceroute to the machine(s) that are failing to see if the problem is a routing failure.
Try doing a tracert and a ping from the NT machine to your Mac Server, if it passes but the above fails maybe you are running a Firewall on this Server which is refusing your IP.
Try Telnet'ing to Port 25 on the NT Machine and see if it comes back with a Welcome message.
When the Mac talks to the NT machine does it have to go through a router to reach it? (Are they connected to different Subnets even if they are physically connected to the same network)
