When the <ComputerName> of the remote computer is resolved by DNS, NBTSTAT -a <ComputerName> returns Host not found because it is broken.
The workaround is:
1. Ping <ComputerName>
2. nbtstat -A <IP address returned by step 1>
NOTE: The problem exists through Service Pack 6a, and may not be fixed in subsequent Service Packs.
NOTE: The problem does not exist in Windows 2000.