Problema con consulta

Estimada lista, buenas noches.
Recurro a ustedes porque tengo un problema que no le encuentro solución:
Me armaron una consulta que se ejecuta de acuerdo al explain analyze de
dos maneras diferentes.
La consulta es simple, con muchos inner joins y en algunos casos se
ejecuta en menos de 1 segundo, y en otros casos, la misma consulta puede
demorar hasta 20 minutos.

involucra 5 tablas, una de ellas es un split que puede llegar a tener
hasta 30 millones de registros mensuales, y está dividida justamente con
un constraint por fecha, en tablas separadas por mes.
El constraint exclusion está activado.

las otras 4 tablas son sencillas, con no más de 5000 registros y la
consulta es la siguiente:

select rep.idregistro as idregistro, mov.d as d, rep.fecha+'-2
hours'::interval as fecha, ev.descripcion from tablagrande rep
inner join tablab mov on rep.d=mov.d and mov.idusuario=XXX
inner join tablac avx on avx.idalarma=rep.idevento
inner join tablad ev on rep.idevento=ev.id
where rep.fecha between '2011-10-18 00:00:00' and '2011-10-18 23:59:59'
and rep.idregistro>(SELECT ultalarma FROM tablae where idusuario=XXX)
and avr.idusuario=XXX and
avx.idtipoaviso=1

Puedo adjuntar el explain analyze de ser necesario, pero creo que el
problema está en como formularon la consulta, y no logro entender por
qué se ejecuta excelente en algunos casos y en otros demora tiempo por
demás.

en general, debería devolver entre 0 y 50 registros como máximo.
tablagigante = 30.000.000 registros mensuales (split, constraints, etc)
tablab 15 registros de 5000 aprox
tablac 8 registros de 2000 aprox
tablad 150 registros.
tablae 1 registro de 500

los planes que utilizaron la misma consulta fueron totalmente distintos,
uno demoró 1 segundo aproximandamente, el otro mas de 3 minutos. lo
unico que cambió de una a otra es el id XXX por YYY, pero nada mas.

Saludos,gracias por cualquier indicio para saber cómo encontrar el
problema y disculpen las molestias.

--
Mario Sileone