Como Remover Items de Lista?

Acho que isso acontece pois o remove vai fazer shift de todos os elementos.
Tenta apenas fazer set a null do índice a ser removido, algo como:

registros.set(indice, null);

Só que isto vai deixar “buracos” null no seu array, a não ser que queira evitar isto e ter que limpar os valores null depois, pode continuar com o remove mas fazendo remove do indice com um contador, que começaria no 0.

registros.remove(indice - counter);

Ordena a lista de indices a remover e depois remove do maior para o menor

A interface List possui o método remove, que é sobrecarregado e aceita como parâmetro um int, referente ao índice a ser removido ou um Object, referente ao objeto a ser removido.
Além disso, possui o método removeAll que aceita como parâmetro uma Collection<?> e cuja lógica de exclusão se baseia em identificar todos os elementos presentes na Collection<?> passada como argumento e remove-os da lista original.
Minha sugestão seria criar uma terceira lista, adicionar os elementos que são referenciados pelos índices a serem removidos e depois invocar o método removeAll

List<?> lista = new ArrayList<>();
for (int i = 0; i < indiceRemovido.size(); i++) {        
    System.out.println("Lista \n"+indiceRemovido.get(i).toString());
    lista.add(registros.get(indiceRemovido.get(i));
}
registros.removeAll(lista);

P.S.: É importante ressaltar que esta, provavelmente, não seja uma solução muito performática.

Obrigadão pela ajuda galera. Utilizei a ideia do pmlm de ordenar do maior para o menor e excluir dessa forma. Obrigado galera.