codice:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
  <head>
    <title>Form</title>
    <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
    <link rel="stylesheet" type="text/css" media="all" href="./css/layout.css" type="text/css" >
    <link rel="stylesheet" type="text/css" media="all" href="./css/form_layout.css" >
    
    <style>
      .error{
        border : 1px solid red;
      }
      
      #error_div{
        color: red;
        display: inline;
        visibility: hidden;
        vertical-align : middle;
      }
      
    </style>
    
    <!--[if lt IE 7]>
     <style type="text/css">
     .error_img { 
        vertical-align : middle;     
        behavior: url(iepngfix.htc) }
     </style>
    <![endif]-->
    
    <script type="text/javascript">
      function checkEmail(inputvalue){
        var pattern=/^([a-zA-Z0-9_.-])+@([a-zA-Z0-9_.-])+\.([a-zA-Z])+([a-zA-Z])+/;
        if(pattern.test(inputvalue)){
          alert("true");
          return true;
        }else{
          
          //alert("false");
          var domEl = document.getElementById('s_email');
          if(!domEl.className)
            domEl.className = "error";
          else{
            domEl.className = domEl.className + " error";
          }
          document.getElementById("error_div").style.visibility = 'visible';
          
          return false;
        }
      }
    </script>
  </head>
  <body>
    <div id="container">
      <div id="top">
        [img]./css_immagini/header.PNG[/img]
      </div>
      <div id="leftnav">
        <ul>[*]Inviare una e-mail cifrata[*]Decriptare una e-mail cifrata[/list]
      </div>
      <div id="content">
      

      

      <div id="form">
      <form action="formmail.php" method="post" class="niceform" name="signupform" onSubmit="return checkEmail(document.signupform.s_email.value)">
        <fieldset>
          <legend>Inviare una e-mail cifrata</legend>
          <dl>
          <dt><label for="email">Email Address: (Sender)</label></dt>
          <dd><input type="text" name="s_email" id="s_email" size="32" maxlength="128" />

                <div id="error_div">
                 
                 Inserire un indirizzo email valido
                </div>

          </dd>
                
          </dl>
          <dl>
          <dt></dt>
          <dd><input type="submit" name="submit" id="submit" value="Submit" ></dd>
          </dl>
        </fieldset>
      </form>
      </div>
      </div>
      <div id="footer">
      Footer!
      </div>
    </div>
  </body>
</html>
in grassetto ho messo le aggiunte al tuo codice

EDIT : modificato, avevo dimenticato la scritta e la gestione delle png per IE6
(
l'immagine la prende da internet in questo caso se la tua immagine non è una png il problema non si pone nemmeno ma per sicurezza te l'ho fatta nel caso non lo sapessi :
iepngfix.htc è uno script che puoi scaricare da qui : ftp.daum.net/eclipse/eclipse.org-common/themes/Phoenix/iepngfix.htc imposta il percorso di una gif 1px*1px

spero di non averti confuso le idee nel caso non lo sapessi ma ho cercato di essere esaustivo
)