As it turned out, the problem was that TCP/IP NetBIOS Helper Service was not running. Starting the service resolved the problem. Once again, NetBIOS is a must.
A particularly bad thing about the TCP/IP NetBIOS Helper Service is that one cannot force it to start via group policy. If the service is not running on a computer, group policy will not apply to this computer, as my example demonstrates.