I've ran into similar oddnesses twice in the past two months. In both
cases, a developper came to me and said that a particular query ran very
quickly the day the table was created and populated, and ran very slowly
starting the next day, after the DB had been VACUUM'ed. In both cases,
their WHERE clause used operations such as concatenations on fields that
did not have indexes. In both cases, creating the indexes speeded up the
query, dropping the cost from some obscene number to a very low one. ( on
the order of 8000 to 60).
I'm not sure why the queries worked well before the database was
VACUUM'ed, but it's happened to me twice now - and it sounds similar
enough to your situation that you may want to look at whether you have
appropriate indexes created on your table.
steve