How about doing a DNS lookup but for a SOA record type, instead of an A record? I'm fairly sure that will either give you a record or an NXDOMAIN.

  $ dig magic.com SOA
  [snip]
  magic.com.              21600   IN      SOA     auth03.ns.uu.net. hostmaster.uu.net. 990605 21600 3600 1728000 21600