The extent of my knowledge regarding DNS is that there needs to be some mapping somewhere between a host name and IP address. That informatino can be locally or gained from a DNS server.
In linux, that information is provided in the /etc/hosts file.
In Windows, the only thing I'm aware of to do somethign similar is setting up printer/file sharing. In doing that, your machine uses an SMB protocol (I think that's the name). When a machine logs on, and is capable of providing shares to other machines, it broadcasts its name on the network, and each machine receiving that broadcast makes a note of that machine name and its IP address. I don't believe that's a true/proper DNS method, but it's results are similar. If you were to set your linux box with Samba, then I'm pretty sure you'd get the results you're looking for.
You didn't mention in your original post whether you could ping your Windows machine(s) from your linux box. My guess is you can't, unless you have an entry for them in the /etc/hosts file.
I guess what I'm suggesting is to install Samba. It's reasonably simple, and it's typically what people with Win/Linux netwoks want (to share files and printers between OSes).