Well, I gotta give it to the LQ, one of the first and still most popular forums. Not that we can't be better.

Anyway, this looks like something that would fit the tips section in blogs, but well, it's ok now.

Thanks for sharing!

You can also have a DNS server act as a proxy like that. This can be central for all the network and can combine NetBIOS proxying with OpenDNS or OpenNIC connectivity.

The DNS server software I chose for this setup is PowerDNS for its ability to get domain names from programs written in any language, including shell. PowerDNS is available in Debian GNU/Linux 3.1 as pdns. (on other distributions, make sure the PowerDNS recursor is installed) So, here comes the script I wrote for it:

#!/bin/bash
# PowerDNS PipeBackend nmblookup glue script
# 
# Copyright (C) 2007 Thomas Jollans
# Ditributed under the terms of the WTFPL 

## CONFIGURATION ##

# your workgroup or domain name, makes xxx.$MYDOMAIN equivalent to xxx .
MYDOMAIN=mshome
# TTL in seconds (time how long a domain name is cached)
TTL=900 # 15 minutes
# where to log to
LOGFILE=/dev/null


## ACTUAL CODE ##
echo >>$LOGFILE $$ started
read -r line0
if [[ "`echo $line0`" != "HELO 1" ]]; then echo FAIL ;fi
echo -e "OK\tNetBIOS back-end is alive and well"
echo >>$LOGFILE $$ shaken hands: "'$line0'"

while true
do
    read line
    quest=($line)
    echo >>$LOGFILE $$ query: "'$line'"
    case ${quest[0]}
    in
        PING)   echo END
                ;;
        Q)      name=`echo ${quest[1]} | sed "s/\.$MYDOMAIN\$//i"`
                echo >>$LOGFILE $$ $name
                if echo $name | grep -s '\.' >/dev/null; then echo END
                else
                    addr=`nmblookup ${name} | grep -v 'querying\|failed' | awk '//{ print $1 }'`
                    echo >>$LOGFILE $$ looking up $name; result: ${addr-none}
                    if [[ -z "$addr" ]]; then echo END
                    elif [[ ${quest[3]} = ANY ]]; then
                      echo -e "DATA\t${quest[1]}\tIN\tA\t${TTL}\t1\t${addr}"
                      echo -e "DATA\t${quest[1]}\tIN\tMX\t${TTL}\t1\t${addr}\t0"
                      echo END
                    elif [[ ${quest[3]} = A ]]; then
                      echo -e "DATA\t${quest[1]}\tIN\tA\t${TTL}\t1\t${addr}"
                      echo END
                    elif [[ ${quest[3]} = MX ]]; then
                      echo -e "DATA\t${quest[1]}\tIN\tMX\t${TTL}\t1\t${addr}\t0"
                      echo END
                    else
                      echo END
                    fi
                fi
                ;;
        "")       exit 7;;
        *)      echo END ;;
    esac
done

now you need to get the DNS server to use this information. Add the following lines to /etc/powerdns/pdns.conf:

launch=pipe,bind
pipe-command=/where/the/script/is

recursor=127.0.0.1:5300

and set the following in /etc/powerdns/recursor.conf:

local-port=5300
local-address=127.0.0.1

Now (re)start the two servers, on Debian with

# /etc/init.d/pdns-recursor restart
# /etc/init.d/pdns restart

and test the setup with

$ host WINDOWS-MACHINE 127.0.0.1

If it works, add the machine to all /etc/resolv.conf files you can find to make it the default name server. It will return addresses (IPv4 only?) for the Windows machines in your workgroup and everything the name servers in the server's resolv.conf know.
If it doesn't, ask here.

Information on how to configure the name server on DHCP-connected clients to come

Right... originally I wanted to ask about this, but when I found the answer I just used the open window

It is not entirely unlikely that you use DHCP to configure your network. In fact, if you did not manually set IP adresses to use on the network and have a permanently running router of sorts, then you almost certainly do. DHCP is also used to get name servers to use, and thus the "DHCP client" overwrites /etc/resolv.conf and thus any name servers you man have manually set.
There are two common GNU/Linux DHCP clients: dhclient and dhcpcd.

dhclient is the more full-featured of the two; it allows you to set extra name servers to add to resolv.conf by adding a line like

prepend domain-name-servers xxx.xxx.xxx.xxx;

to /etc/dhclient.conf.

dhcpcd is extremely basic; it allows no customization of /etc/resolv.conf whatsoever. It only has a command-line option -R that prevents overwriting the same. This is impractical on the DNS server, which needs to contact DNS servers with possibly dynamic IP addresses, but totally unproblematic on the other machines: set the local DNS server in /etc/resolv.conf and make sure that the option is set. On Gentoo Linux, this is done by adding the line

dhcpcd_eth0="-R"

to /etc/conf.d/net, on other distributions you might have to edit some script in /etc/init.d or /etc/rc.d/init.d.