I'm having the same situation. As soon as the ACEs are not in the right order (starting at 0, incrementing +1 each ACE) the ACL can't be saved.
Someone who can help us out?

Haven't tried implementing/tweaking this code by samsamm777 from issue #3715 yet, seems it might work to select the ACE to remove.

$classACEs = $currentAcl->getObjectAces();
for ($i=(sizeof($classACEs)-1); $i>=0; $i--)
{
    if ($classACEs[$i]->getId()==$request->get('ace'))
    {
        // Find out if the ace has master or owner, and prevent the delete.
        echo $classACEs[$i]->getMask();

        //$currentAcl->deleteObjectAce($i);     
    }
}

Will post an update if this works.

Seemed a false alert. Got it solved with this:

// get ACL
$aclProvider = $this->container->get('security.acl.provider');
$objectIdentity = ObjectIdentity::fromDomainObject($object_to_remove_from);
try {
    $acl = $aclProvider->createAcl($objectIdentity);
}catch(\Exception $e) {
    $acl = $aclProvider->findAcl($objectIdentity);
}

// Get all aces and try to get ACE for user to fire
$aces = $acl->getObjectAces();
foreach($aces as $i => $ace) {
    if($ace->getSecurityIdentity() == $firedSID)
    {
        // Got it! Let's remove it!
        $acl->deleteObjectAce($i);
    }
}
$aclProvider->updateAcl($acl);

Had an ACL to test on with 4 ACEs on it (orders 0, 1, 2, 3)
In test runs, I removed one of the ACES and checked if the order in acl_entries was consistent. In all four cases I got a consistent order (0, 1, 2)

I had this same issue. In fact my indexes were ok, but when multiple indexes were deleted in one pass, it failed. Solved by reversing the order of the loop as described by @Buurman14 above

Closing this issue as ACLs are not part of Symfony Core anymore (see #14718 for the initial discussion). It the issue still exists, you can create an issue on symfony/security-acl or symfony/acl-bundle. Thanks.