Lo que se me ocurrio es darle un nombre a cada checkbox y luego cuando el usuario presiona el boton eliminar cargar los que estan tildados en un array y buscarlos en la bd para eliminarlos, pero no tengo mucha idea de como hacero..
Código:
  
 <table width="100%">
  <tr>
    <td>
	<?
	$nickUsuarioL = $_SESSION["nick_usuario"];
		
	if($accion == "borrar"){
			
	        $SQLborrar = "DELETE FROM mensajes WHERE msgid IN(".implode(', ', $HTTP_POST_VARS['mens']).")";
		mysql_query($SQLborrar);
			
		echo "<font face=Tahoma size=2><b>Mensaje Borrado</b>";
		
	} 
	else {
		
		$sql= mysql_query("SELECT * FROM mensajes WHERE para = '$nickUsuarioL' ORDER by msgid DESC"); //aki esta la var del sistema de JLMM
			
		while ($row = mysql_fetch_array($sql) ){
			
			$asunte = $row[asunto];
			$resto = substr("$asunte", 0, 40);
			$aydi = $row[msgid];
				
			echo "
			<tr><td bgcolor=#EEEEEE width=10><font face=Tahoma size=1><input type=checkbox name=\"mens[]\" value=$aydi></font></td>
			<td bgcolor=#EEEEEE
			<font face=Tahoma color=black size=1><center><i>".$row["de"]."</i></center></font></td>
			<td bgcolor=#EEEEEE><a href=?go=usrpanel&admin=leer_mensaje&id=".$row[msgid]."><font face=Tahoma color=black size=1><u>$resto..</u></a></font></td>
			<td bgcolor=#EEEEEE width=100><font face=Tahoma color=black size=1>".$row["fecha"]."</font></td></tr>";
			
		}
		?> 
			
		</table>
		<br>
		<table width=340 align=center cellspacing=2 cellpadding=2>
		<form method = "POST" action = "<?=$_SERVER[PHP_SELF]?>?admin=ver">
			<tr>
				<td>
					<input type=radio name=accion value=borrar>
					<font face=Tahoma size=1> Borrar</font>
				</td>
				<td>
					<a href=enviar_privados.php>
						<font face=Tahoma size=1> <u>Enviar Mensaje</u></font>
					</a>
				</td>
				<td>
					<input type="submit" value="Enviar">
				</td>
		</table>
		</form>
			
	<?
	} ?> 
    </td>
  </tr>
</table>
 
 


