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