If you need to check for instance if “ns1.titov.net” is a registered nameserver and can be filled as nameserver for a domain you can do it this way:

ask which nameservers are authoritative for zone “net” with:

dig ns net

in the answer section you will have:

net. 172800 IN NS l.gtld-servers.net.
net. 172800 IN NS m.gtld-servers.net.
net. 172800 IN NS a.gtld-servers.net.
net. 172800 IN NS b.gtld-servers.net.
net. 172800 IN NS c.gtld-servers.net.
net. 172800 IN NS d.gtld-servers.net.
net. 172800 IN NS e.gtld-servers.net.
net. 172800 IN NS f.gtld-servers.net.
net. 172800 IN NS g.gtld-servers.net.
net. 172800 IN NS h.gtld-servers.net.
net. 172800 IN NS i.gtld-servers.net.
net. 172800 IN NS j.gtld-servers.net.
net. 172800 IN NS k.gtld-servers.net.

than you should ask all of the nameservers for IP addres of the host in question:
host ns1.titov.net i.gtld-servers.net

if you got a respoce from any one of the servers, than you have a valid nameserver:
Using domain server:
Name: i.gtld-servers.net
Address: 192.43.172.30#53
Aliases:

ns1.titov.net has address 66.230.155.157

You can use this PHP code to accomplish this, I know it’s ugly, as it uses shell commands and regular expressions to parse their output, but I was not feeling like implementing the DNS protocol. Dig and host commands are part of bind package and should be installed on most servers:

function isValidNs($ns){
  $tld='com';
  if (preg_match('#\.([a-z]+)$#', $ns, $m))
    $tld=escapeshellarg($m[1]);
  $ns=escapeshellarg($ns);
  $dig=`/usr/bin/dig ns $tld`;
  preg_match_all(\"#[a-z\.]+\.\s+\d+\s+IN\s+NS\s+([a-z0-9\.\-]+).#\", $dig, $m);
  for ($i=0; $i<count($m[1]); $i++){
    $server=escapeshellarg($m[1][$i]);
    if (preg_match('#has address#', `/usr/bin/host $ns $server`))
      return true;
  }
  return false;
}

Note that you should as all of the nameservers, as for instance Bulgarian nameservers seem to be broken and only one of eight (maybe the master) nameservers responsible for “bg” zone replies to such requests.