[[duilioisola]]

Prueba con la sentencia EXISTS().

Cuando haces un SQL con "Campo IN (select ...)" el motor de base de datos tiene que obtener los datos del select y luego hacer la comparación.
Con "EXISTS (select ...)" solo recorre los datos y se para cuando existe el primero. No tiene que guardar los datos que recupera del select en memoria.

Código SQL [-]
select a.codprv, a.codigo, a.apellidos, a.nombre, a.referencia, a.situacion, a.f_alta, b.cuota
from persona a, cuotas b
where
a.codprv = rvins and
/*
a.codigo not in (select distinct codigo
                 from recibos
                 where
                 codprv = a.codprv and
                 refint like '1%' or refint like '2%') and
*/
not exists(select codigo
           from recibos
           where
           codigo = a.codigo and
           codprv = a.codprv and
           (refint starting with '1' or refint starting with '2')) and
a.codprv = b.codprv and
a.codigo = b.codigo and
b.tipo = 'A' and
b.cuota > 0

La tabla Recibos tiene como clave primaria CodPrv, Codigo, Fecha y RefInt

Además, puedes probar a cambiar el orden de la clave primaria para que codigo, codprv y refint sean los primeros campos y fecha el último.
Quizás ayude, pero puede ser que haga que otras consultas vayan mas lentas.

NOTA:
La parte "(refint starting with '1' or refint starting with '2')" ponla entre paréntesis para "desambiguar" la sentencia.