Here are details of the machine I want to access using its hostname:

    $ hostname
    hostname
    $ cat /etc/hosts
    127.0.0.1	localhost
    127.0.1.1	hostname.company.local	hostname

It's a default Debian 6 (Squeeze) install, so I didn't fiddle with anything yet.

This is what I get from a machine (running Debian Unstable) trying to access above machine:

    $ ping hostname
    ping: unknown host hostname
    $ ping hostname.company.local
    ping: unknown host hostname.company.local
    $ cat /etc/resolv.conf
    nameserver 192.168.2.21
    nameserver 192.168.2.51
    search company.local