How can we troubleshoot a NetBIOS/firewall issue related to MSDTC? (Funny twist included)

A friend of mine have two servers with MSDTC connecting to two SQL Servers. Everything is fine to one SQL Server, but to the other he often gets error:

Communication with the underlying transaction manager has failed. —>
System.Runtime.InteropServices.COMException: The MSDTC transaction
manager was unable to push the transaction to the destination
transaction manager due to communication problems. Possible causes
are: a firewall is present and it doesn’t have an exception for the
MSDTC process, the two machines cannot find each other by their
NetBIOS names
, or the support for network transactions is not enabled
for one of the two transaction managers. (Exception from HRESULT:

The only difference between the two SQL Servers is network (different subnet) and firewall (the one where it’s working has less restrictions). And here is the funny part, if one browse a share from the SQL to one of the two servers that is not SQL, everything works fine for a while. They suspect something with NetBIOS name resolution, but they cannot troubleshoot it in detail.

Any ideas?