Just thought of a very simple test you could run, Michael. Is the plan
identical for the following query on the old and new server?

select *
from rdb$database
where not exists(
select v509Index
from VAREFRVSTR_DETAIL
where VarePlu_ID=:PVarePlu_ID and
      Afdeling_ID=:AfdNr and
      Farve_Navn=:PFarve_Navn and
      Stoerrelse_Navn=:PStoerrelse_Navn and
      Laengde_Navn=:PLaengde_Navn)

Set