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