[PGSQL 8.3.5] Use of a partial indexes

HI all.

I have a 8M+ rows table over which I run a query with a and-only WHERE
condition.
The table has been periodically VACUUMed and ANALYZEd.
In the attempt of speeding that up I added a partial index in order to limit
the size of the index. Of course that index is modeled after a "slowly
variable" part of the WHERE condition I have in my query.

And timings actually dropped dramatically (I do know the problems with caching
etc. and I paid attention to that) to about 1/20th (from about 800ms to
average 40ms, actually).
So I turned to EXPLAIN to see how the partial index was used.
Incredibly, the partial index was not used!
So I tried to drop the new index and incredibly the performances where still
very good.

While I can understand that the planner can decide not to use a partial index
(despite in my mind it'd make a lot of sense), I'd like to understand how it
comes that I get benefits from an enhancement not used!
What'd be the explanation (if any) for this behavior?

Thanks.

--
Fahrbahn ist ein graues Band
weisse Streifen, grüner Rand