Lo más trivial...

Código:
<form name="usuarios" action="eliminar.php" method="POST">
    <input type="checkbox" name="user1" value="">
    <input type="hidden" name="idUsuario1" value="134057">

    <input type="checkbox" name="user2" value="">
    <input type="hidden" name="idUsuario2" value="168967">

    <input type="checkbox" name="user3" value="">
    <input type="hidden" name="idUsuario3" value="147526">

    etc...

</form>
tu script php... (eliminar.php):

Código:
//$numUsers = numero Usuarios;

for ($i = 1; $i<=$numUsers; $i++){
  if (isset($_POST["user".$i]) && (isset($_POST["idUsuario".$i])){
    if ($_POST["user".$i] == 'on'){
       if (existeUsuario($_POST["idUsuario".$i])){
          eliminarUsuarioPorSuId($_POST["idUsuario".$i]);
       }
    }
  }
}
Cuidadín con la seguridad y con las cosas inesperadas.