Since native NetBIOS broadcasts are out, your options are either to use WINS, or rely on AD/DNS. WINS is dead and gone in most networks today... so I wouldn't rely on that. Your options may be even further limited to a lack of AD support in Samba3. Sadly, Samba4 hasn't even reached the "beta" status yet.
Straight from the samba wiki:
Use of raw SMB over TCP/IP (No NetBIOS layer) can be done only with
Active Directory domains. Samba is not an Active Directory domain
controller: ergo, it is not possible to run Samba as a domain
controller and at the same time not use NetBIOS. Where Samba is used
as an Active Directory domain member server (DMS) it is possible to
configure Samba to not use NetBIOS over TCP/IP. A Samba DMS can
integrate fully into an Active Directory domain, however, if NetBIOS
over TCP/IP is disabled, it is necessary to manually create
appropriate DNS entries for the Samba DMS because they will not be
automatically generated either by Samba, or by the ADS environment.
In short, in a modern AD environment, DNS is more commonly used for workstation name lookups... samba can use DNS for lookups, but does not have any way to register itself properly with Microsoft DNS servers. (samba4 has some work-arounds that do a better job... but samba4 can also do AD). You can manually add a DNS record on the DNS server directly, but if your IP should change... you would have to manually update the DNS records.