A concept based off of a silly tweet I saw the other day: automatically naming new hosts using word lists. If you used an adjective-noun-verb pattern, each host would be named after a random but syntactically valid English sentence.
So you have a combination of auto-generated and mass-produced, but also memorable when required.
Their approach was more simplistic: a list of 256 words and just swapped out a word for each part of the EC2 internal IP address.
I wouldn't tie it to IP addresses myself, although that's not a terrible idea, especially if you have a lot of short-lived nodes that you don't do a lot of configuration to (probably using a bundled image).
I wasn't sure if this was worth doing for the instances at my day job, but it turned out to be quite useful and I hacked together a little tool to automatically generate names, server-name, using a simple combination of colour and animal-name word lists. This gives us memorable unique parts like 'yellow-alligator', while still being easily integrated into our automated node-creation processes.
The command can take additional information to include in the name - we started out with nodes named like 'staging-office-app-cherry-coyote', but decided that while including the node role in the hostname was immediately useful, it made for cumbersome names and caused problems with node reuse (such as when 'prod-office-db-slave-teal-squid' gets promoted from slave to master) so now we just prepend the environment ('prod' or 'staging'), which I like to keep in the hostname so I can do hostname-based globbing in my ssh config.
In an ideal world we'd throw away instances at the first sign of trouble, and naming wouldn't really matter. In practice, instances can be long-lived and being able to refer to a specific instance with a meaningful name can be useful for debugging or application health-monitoring.