So I use almost exactly the same approach except in the VPN configuration options (I use Ubuntu 12.04) I just set the search domain to my-internal-name.blah, as well as, making sure the VPN connection is only used for resources on its own network.

Then as part of my bootstrapping I register the VPC instance's internal-ip address on route53 under the my-internal-name.blah zone.

Then I can simply do ssh staging01, etc.