I found this answer to my question but if the DNS cache for existing.mydomain.com is the problem, wouldn't that solution just result in a infinite circular loop? Or does a DNS lookup for newsub.mydomain.com force a DNS refresh for all subdomains of mydomain.com?
newsub.mydomain.com points to the new server.
existing.mydomain.com points to the new server for users who have checked recently, and the old server for those who have not.
The old server redirects to newsub.mydomain.com with a 301 "permanently moved".
There is no loop.
However, you still have to keep the old server running until the DNS TTL for existing.mydomain.com expires. If you don't, some users might hit the old IP and think your site is down.