Active Directory Domain where FQDN and NetBIOS name are the same

I have "inherited" an ancient domain (NT4, then upgraded to Win2000 Mixed Mode and now running on Win2003) where the NetBIOS name coincides with the DNS/FQDN one, and this is giving us problems with remote clients which need to be joined to the domain.

Lets the domain be called EXAMPLE: it is both the NetBIOS name and the DNS name, as can be seen by opening the DNS administration panel. Inside the local LAN, apart some occasional confusion on what protocol is resolving the machine's name, this arrangement seems to work.

On remote LANs (connected by VPN), problems happen: the remote client can not connect to the domain. The error message states that the DNS query correctly returns the domain controller list, but no domain server can be contacted. From a connectivity standpoint, all ports are opened inside the VPN, so this is not due to ACL and the likes.

Rather, using Wireshark to examine the exchanged packets, I can see many (failed) NBNS queries – in other words, the remote PC is using NetBIOS broadcast resolution method to find the domain controller. This is clearly going to fail, as NetBIOS is a non-routable protocol by design.

In short, it seems that when entering a NetBIOS-style domain name in the "Member of domain:" GUI panel, Windows only uses NetBIOS to resolve/find the domain controllers, with no DNS fallback. In some manner, this can even expected: after all, EXAMPLE is not a valid DNS name (however, I wonder why the domain creation wizard let this happen in the first case, but I digress…).

So work-around the problem, I tested some solutions:

• sidestep the problem entirely, joining the PC to the domain when it is on our local LAN for OS installation/preparation (it clearly can not be done for client already deployed on remote locations)
• use an appropriately-crafted lmhosts file
• installation and use of WINS

The last approach (WINS) seems clearly better, as it avoid distributing a (potentially changing) lmhosts file to the remote clients. However, I would like to solve the problem once for all.

So, my questions are:

• can I force Windows to use DNS names rather than NetBIOS (note: I already tried to disable NetBIOS name resolution on the NIC properties page, with no avail)
• can this situation be normalized without radically change the current domain?
• new one: can I add something like a "DNS domain alias" to assign a correctly-formed FQDN name to the current AD domain?
• can the domain be renamed? If so, what problem can I expect doing that?
• if all the above is "no", is the best approach to create a new domain, gradually migrating the current client/server on the new one?

Thanks.