How can I get Windows to see Linux host names and vice versa?

ARP host names are different from NetBIOS names.

Windows bases itself on NetBIOS names where as Linux bases itself on the host names.

Your router receives the host names through ARP / DHCP; yes, Windows does have host names too.

---

You need to have your router host the hostnames in it's DNS or you'll need to adjust all the hosts file.

If your router doesn't support it, you could look into installing DD-WRT on your router and using dnsmasq together with a hosts file where you will fill in the hosts. I would deem that's pretty much a work-around though, do you really want to do this just to be able to ping? Not a daily computer activity...

I know your pain, it's completely insane that in 2011, host names don't just "work", right out of the box.

Another option is Bonjour. It's an Apple technology, but there are implementations for Linux (Avahi) and Windows (Bonjour for Windows). Bonjour let's you access other computers using the syntax:

<hostname>.local

I went with this solution, because I don't have a DD-WRT compatible router, or an always-on server to run DNS. Also, once its set up, you don't have to worry about whether an IP changes, like with a hosts file.

You need a name resolution server of some sort.

First setup a DNS server that accepts dynamic updates on one machine that has a static IP. BIND is the obvious choice (installs on Windows and Linux) but there are other Linux versions that work just as well such as DJBDNS etc... Your DNS server will need to forward requests to your ISP's DNS server or to some other public DNS server. A good domain name that should be safe enough to use is "home.internal" No need to register it and it is not a public domain... This machine you set DNS onto will need to be up all the time...

Once that is setup, tell your reouter's DHCP server to hand out the IP of the DNS server you just setup.