MySQL tablosunda mail adresi ve domaini sanırım ayrı tutmuyorsunuz, fakat mysql sorgusunda;

MAILADRES='$MailDomain'

Bu şekilde kullanmışsınız dolayısıyla mail domainin pas geçmesi gayet normal bir durum gibi görünüyor, bunun yerine ilgili mail domainini LIKE komutu ile yaparsanız sanırım sorununuzu çözebilirsiniz.

$MailDomain=end(explode('@',$EMail)); 
    $sql="SELECT MAILADRES FROM YASAKLIMAILLER WHERE (MAILADRES='$EMail' or MAILADRES LIKE '%".$MailDomain."%')"; 
    $rs=mysql_query($sql); 
if(mysql_num_rows($rs)>0){    
      echo "<script>alert('Your e-mail address is prohibited. Please try another e-mail address.'); window.location='index.php';</script>"; 
    }else{ 
   .......