As one of anti-spam technologies, DNSBL based on the URLs or their corresponding IP addresses in the messages is well used. However, some spam mails cannot be filtered by conventional DNSBLs since the spammers create websites using various techniques such as botnet, fast-flux and Wildcard DNS record. To discriminate such spam mails, we ananalyzed DNS record characteristics corresponding to the domain name in the URLs in actual spam mails. According to this analysis, in this paper we propose a spam mail discrimination system based on the behavior of DNS servers. Since the behavior checking process is likely to wait for a timeout, the system queries some records to a DNS server simultaneously and decides whether the mail is spam or not on receiving the first reply. In addition, the system also introduces a blacklist for the IP addresses of the DNS servers.