What you described above sounds correct… you’d need a Virtual Server with that name, but with the BIND DNS Domain feature disabled.
And then, since DNS is hosted at a third party service – you’d just need to make sure that the nameservers for mydomain.com point to that third party service.
It doesn’t matter whether it’s an A record or a CNAME, it just needs to resolve to your server.
The errors you’re receiving sound like DNS issues though… are you sure that mydomain.com has it’s nameservers pointing at your third party provider?
If you’re able to provide the actual name of your domain name, that would aid in troubleshooting… you can always edit out the name from this post after we figure out what’s going on