In order for LAN to LAN based games to work in these older games, you have to install the IPX/SPX protocol. This is an ancient protocol that was used when Windows XP was still a big thing. In windows Vista and higher, the IPX/SPX protocol has been disabled because its successor TCP/IP can do it much better.
Some of the older games got patched to search the internal LAN using the TCP/IP protocol. Given that their game already does support the TCP/IP protocol to play over internet, its strange they kept the IPX/SPX protocol for the lan environment though.
If you do not want to install the IPX/SPX protocol on either machine, you can use software like Tungle or Hamachi which are VPN clients. They do install the IPX/SPX protocol when you activate their services which is why even if you are in the same LAN, using one of these services does make it work.
To add the IPX/SPX protocol, do the following (works for windows Vista and 7, not for windows 8):
Go to Control Panel > Network and Sharing Center > Change Adapter Settings
Double click your network adapter.
Press Properties
Press Instal...
Choose Protocol and press Add...
Select IPX/SPX protocol and install it.
Reboot the pc.