Nautilus network browse list problem

[Andreas Heinlein <aheinlein gmx com>]

Hello,

we are currently in the process of migrating a Windows network to
Ubuntu. In the transition, we are still heavily using SMB filesharing.
The windows machines form a domain controlled by a samba PDC on Debian
Linux.
Under windows, I can see all machines in the network neighborhood as
soon as they are online. In nautilus, it can take up to one hour for
them to appear under "Places"->"Network". They are immediately available
if using "Connect to server..." and entering the name manually.
Refreshing the list via F5 or the refresh button does not help.

What might be causing this? What methods does nautilus use for creating
the list of available computers, and which are preferred? Currently, we
have the choice between WINS (implemented by the Samba PDC) and plain
old windows browse lists with the samba PDC being the master browser. We
do not have something like active directory, though we have DNS
resolution for all clients and also a LDAP server at hand.
Would there be other methods like DNS-SD (using static DNS entries, not
mDNS) which are more reliable?

Thanks,
Andreas