Sounds to me like this is some kind of resolving issue.
W2k and XP clients use DNS as their primairy means of resolving names to IP adresses. Same goes for the domain name, this is resolved with a SRV record on the DNS server. When DNS doesnt work they can fall back to Netbios resolution. (though this order can be changed in the registry)
Win9x clients and NT4 use Netbios as their primairy means of resolving. Sounds like they are having some trouble. This would also explain why it takes so long to create a browse list, as this is generated by Netbios broadcasts (and is thus slow to build up initially), if no WINS server can give the client a complete list.
Now I was under the impression that Netbios names could not contain a colon, and thus, bearing in mind that Win9x clients will use Netbios first, I had not expected that a domain.com name with a colon, would be a valid domain for these kind of clients, but since you seem to have used this succesfully in the past, I may be wrong on this point.
W2k and XP have no problem at all with DNS domain names, as its their primary resolving method anyway.
So to me it sounds like you are having some Netbios, WINS or Broadcast problems on your network. If you are currently not running a WINS server, (some admins turn this off once they migrate to W2K), considder turning it back on for hte sake of your 9x clients. It will jsut make their life a lot easier. Remember to integrate the DNS and WINS, saves a lot of admin overhead, and keep in mind security considderations when it comes to WINS, its never as secure as secured-DNS.