Server Avahi – Access Server by Host Name

First, make sure you have the Avahi daemon installed. (Should be installed by default on Ubuntu Desktop, but not on Server.)

sudo apt-get install avahi-daemon

Then to access them, add ".local" to the end of the name, for example

ssh machinename.local

I'm not sure if it's possible to remove the need to add .local

The problem described here may not be related to DNS at all.

You have to know that Windows can resolve the Windows hostname to its IP via other mechanisms than standard DNS : NetBIOS lookup, WINS, ...

As you said you have Samba installed on your Ubuntu, this is probably what's happening. On all of your Windows machine, it is possible, out-of-the-box, to have the Windows name resolved to its IP address. As Samba is installed on Ubunut, for your Windows PC, they see the Ubuntu PC as a Windows PC and the same resolution is possible.

You tell that you run net view on Windows and you see your Ubuntu PC, so the NetBIOS name is well published on your network, so it works from Windows.

To achieve the same behaviour on Ubuntu as on Windows, you have to install and configure additional pieces of software. What you need is to add a lookup library that will allows Ubuntu to convert NetBIOS names to IP. This library is contained into the libnss-winbind package.

As any other Ubuntu packages, you install it by doing sudo apt-get install libnss-winbind. May be the library is already installed, you can check it presence by doing dpkg -l|grep libnss-winbind.

Once the library is installed, you have to enable it in the /etc/nsswitch.conf file. This file is the configuration file for the NSS (Name Service Switch), which defines from which sources Linux is able to resolve hostname, usernames, groupnames and so on.
In this file, you already have a line starting by hosts:, probably looking like this

hosts:          files dns

This tells your system to first look into the /etc/hosts file and then into the configured DNS to resolve hostnames.
You have to modify this way :

hosts:          files dns wins

Note that the order of the words files, dns and wins are important. First, the system will check the local file for resolution, then will ask the DNS server and finally, if not yet found, will perform NetBIOS lookup.

Once this is updated, to function correctly, you also need to have the winbind service running. The package containing it is a dependency of libnss-winbind, so it has been installed along it.
Do service winbind start to activate it.