Internal DNS inside Amazon AWS VPC

Instances should register their DNS names with your DNS servers via DDNS when they start (as CNAMEs to their public AWS-assigned FQDN); that way you can refer to them by well-known name and get the most appropriate address (internal or external) regardless of where you are. Route53 probably has this sort of magic built-in, but I prefer provider-independent solutions where possible.

It seems from the AWS VPC documentation that the recommended approach to leveraging a DNS server inside of an AWS VPC is to first create a DHCP Options Set and associate it with the VPC. Then you can stand up 1-4 DNS servers in that VPC. Additionally, the DHCP Options Set will allow you to setup the following for all contained VPC instances. (snipped from the docs)

DHCP Option Name      | Description
 domain-name          |  A domain name of your choice (for example, example.com).
 domain-name-servers  |  The IP address of a domain name server.
 ntp-servers          |  The IP address of a Network Time Protocol (NTP) server. 
 netbios-name-servers |  The IP address of a NetBIOS name server.
 netbios-node-type    |  The NetBIOS node type (1, 2, 4, or 8).

Wouldn't something like Avahi work? This is even installed and nicely packaged for most Linux distributions. Just give each instance that needs to be reachable a unique hostname, and Bob's your uncle.