DNS Azure CNAME problem

Question

It takes 9 seconds for a my domain oratorius.com to be resolved, if I use the nslookup command I have to set the timeout to 9 seconds, otherwise I get a timeout. Users have problems getting to my site. My domain host'er says:

The delay is not occurring on our end, you have CNAME records directed to oratorius.cloudapp.net which is where the delays seem to be coming from. You need to contact the DNS administrators for this hostname to find out what the problem us.

Are anyone else having the same issue with Azure? How should I start troubleshooting?

Here is some proof:

C:\Windows\system32>nslookup oratorius.com
Server:  ad3.example.no
Address:  10.1.1.10

DNS request timed out.
    timeout was 2 seconds.
DNS request timed out.
    timeout was 2 seconds.
 Request to ad3.example.no timed-out

C:\Windows\system32>nslookup
> set timeout=9
> oratorius.com
Server:  ad3.example.no
Address:  10.1.1.10

Non-authoritative answer:
Name:    oratorius.cloudapp.net
Address:  65.52.66.8
Aliases:  oratorius.com

Answer 1

But you can't have a CNAME record for oratorius.com (CNAME records can only exist for subdomains, like www.oratorius.com), right?

You should be able to directly check the DNS resolution time on oratorius.cloudapp.net, right? When I ping www.oratorius.com or oratorius.cloudapp.net, both seem to resolve at about the same speed.

(I can't get nslookup to look anything up...)