[__cadetill]

Bueno, puedes probar tambien lo que comenta jplj, es decir

for j := TreeView1.Items.Count - 1 downto 0 to

o bien con el while que te comentaba

J := 0;
while J <= TreeView1.Items.Count - 1 do
begin
  if (Cadena = TreeView1.Items[J].Text) Then
  begin
    DeleteFile(OpenDialog1.FileName);
    TreeView1.Items[J].Delete;
    MessageDlg('El archivo ha sido borrado con exito',mtInformation,[mbOk],0);
  end
  else
    inc(J);
end;

La diferencia del while con el for, es que cada iteración se evalua la expresión y, aunque borres un Item, al evaluarse la expresión sabrá si continuar o no. Fíjate que sólo se ha de incrementar el contador J si no se borra ningún Item