Otra cosa a tener en cuenta es que Delete ya sitúa el cursor en el siguiente registro; por eso, cuando hagas Delete, no llames a Next (aunque no veo cómo puede influir esto para que te borre todos los registros):
Código:
Tabla.First;
while NOT Table.EOF do
if Condiciones then Table.Delete
else Table.Next;