If I remember correctly, your arp table doesn't have to be complete. Assuming your Lan is on a Switch instead of a Hub, it shows the hosts your machine was connected with previously somehow. And I don't think entries are automatically deleted from the table if a host goes offline or is added when a new one comes online.
Your switch has it's own arp table (probably most complete if your Lan only has 1 switch). So has your router and your gateway.
As for hostnames, I think you can only get them via lookups.
IP Scanners basically do ping sweeps over the subnet to see if certain ports respond. If it does, then it does a lookup for the hostname.Although a bit overkill (and not installed by default) but 'nmap' is an all-in-one tool for these kind of things.