Index seems "lost" after consecutive deletes

I've a table "A" with 4,000,000 records.

I've decided to delete records from oldest to newest but I can't delete
records that have references in tables "B", "C" or "D".

so, I've

with qry as (

select A.id

from A

where not exists (select 1 from B where B.a_id = A.id)

and not exists (select 1 from C where C.a_id = A.id)

and not exists (select 1 from D where D.a_id = A.id)

and A.creation_date < (now()::date - interval '12 month')

order by A.id DESC

limit 2000

)

delete from A where id in (select id from qry);

All three referenced tables have indexes (B.a_id; C.a_id; D.a_id) in
order to make query faster.

So for first 2 million rows it worked really well, taking about 1 minute
to delete each group of 2000 records.

Then, after a while I just started to get errors like:

ERROR: update or delete in "A" violates foreign key "fk_C_A" in "C".

DETAIL: Key (id)=(3240124) is still referenced by table "C".

Seems to me that indexes got lost in the path - the query is really specific and no "C" referenced records can be in my deletion.

Has anyone faced a behavior like this?

Am I doing something wrong?

--
Atenciosamente,

Edson Carlos Ericksson Richter