Strange that you need dedicated DNS services to refer to machines by name... my network looks like this:
DSL modem ---> wireless router ---> various computers
...and I can refer to each computer by name to connect to them. They're a mix of Windows computers, Mac computers and Linux computers -- none of which run any DNS servers. I can access the Windows computers by name via SMB from both the Mac and Linux machines, and I can access the Mac computers via SMB/FTP/SFTP/SSH from the Linux and Windows machines by name. I am also using DynDNS for outside access (SSH, VPN, FTP, SFTP, RDC) and have the proper ports forwarded on my router (which also handles the updating of the DynDNS servers -- go D-Link!). This setup is not double-NATted.
Have you tried setting up your network similar to mine? Just a modem to a router, and all computers accessing the router (either via wired or wireless connections)?