XP cannot join NT domain

When trying to add an XP Pro PC to our NT 4.0 domain across a router, I receive the “cannot find domain controller” error. Yet I can browse to the DC! On the network local to the DC, the same PC (I carried it down the street) will join. I have a valid LMHOSTS, a valid admin account, valid DNS, enabled netBIOS over TCP/IP. I even installed a WINS server, and directed the PC there. Microsoft assures us we do not need an Active Directory server to join XP to the the NT domain. Is that right? What else can I try?