Problems (bug?) with the Postgres 8.4.4 optimizer

Hi everyone.
I am using Postgres 8.4.4 on a large-ish amount of data and recently noticed
that my application got very slow at times. I quickly discovered that a
specific query was triggering a sequential scan despite suitable indices
being available. The query in question looks like this:
"select * from kvstore where deviceid = 7 AND (locid >= 1410929 AND locid <=
1690468) OR (locid = 1690469 and locid <= 1690468)"

Note that the last condition (locid = 2 AND locid <= 1) can never be
satisfied.
Now, the Postgres optimizer seems to believe that a sequential scan of 16
million rows is the right way of approaching this query, despite having
accurate statistics (I ran VACUUM ANALYZE before to ensure everything is
up-to-date).

However, if I remove the last part and query for "select * from kvstore
where deviceid = 7 AND (locid >= 1410929 AND locid <= 1690468)", indices
are used and everything works nicely. And I believe that the optimizer
should remove an invalid query, or at least handle it gracefully (e.g. use
it as a parameter for a range query). Since it doesn't do that, I am a
little stumped as to what the correct course of action for me is. I could
try to manually remove "invalid" parts of my query, but then again I don't
want to be patching queries to accommodate a stubborn optimizer if I don't
have to... maybe I stumbled upon a bug?

One more thing, while I'm already writing this message: Maybe someone can
explain why for the above (working) query, and given a primary key on
(deviceid, locid) Postgres decides to do a after a Bitmap Index Scan there
is always another Bitmap Heap Scan