Consulta toma 100 Minutos!!??

Hola

Soy nuevo en postgresql, tuve que instalarlo porque Access no fue
capaz de soportar las consultas, instalé postgres en una maquina con
Windows XP ( No puedo usar linux, porque es el computador del trabajo
),

Estoy realizando una consulta, y toma mucho tiempo en realizarse, como
100 minutos en un P4 de 2.8Ghz 512Mb RAM, la consulta es la siguiente:

SELECT "Rut Cliente"
FROM "Internet_Abril"
WHERE "Rut Cliente" NOT IN ((SELECT "Rut Cliente" FROM
"Internet_Enero") UNION (SELECT "Rut Cliente" FROM
"Internet_Febrero") UNION (SELECT "Rut Cliente" FROM
"Internet_Marzo"));

Todas las tablas tienen indices creados( Rut Cliente es VarChar ), y
las tablas tienen 50.000 registros en promedio.

El explain de la consulta arroja lo siguiente.

"QUERY PLAN
Seq Scan on "Internet_Abril" (cost=19406.67..62126112.70 rows=24731 width=13)
Filter: (NOT (subplan))
SubPlan
-> Materialize (cost=19406.67..21576.07 rows=136740 width=13)
-> Unique (cost=17784.23..18467.93 rows=136740 width=13)
-> Sort (cost=17784.23..18126.08 rows=136740 width=13)
Sort
Key: "Rut Cliente"
-> Append (cost=0.00..3741.80 rows=136740 width=13)
-> Subquery Scan "*SELECT* 1" (cost=0.00..1233.38
rows=45069 width=13)
-> Seq Scan on "Internet_Enero" (cost=0.00..782.69
rows=45069 width=13)
-> Subquery Scan "*SELECT* 2" (cost=0.00..1104.06
rows=40353 width=13)
-> Seq Scan on "Internet_Febrero" (cost=0.00..700.53
rows=40353 width=13)
-> Subquery Scan "*SELECT* 3" (cost=0.00..1404.36
rows=51318 width=13)
-> Seq Scan on "Internet_Marzo" (cost=0.00..891.18
rows=51318 width=13)

Cualquier ayuda se agradece, tengo que hacer 30 consultas similiares
para obtener los datos para mi tesis.

saludos
Christian