Problems (bug?) with the Postgres 8.4.4 optimizer, 2nd try

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 Bitmap Index Scan followed by a
Bitmap Heap Scan, rather than a simple Index Scan on the perfectly matching
index? I can even simplify this problem: When I issue this query: "select *
from kvstore where deviceid = 7 AND locid = 1410929" my primary key index is
used in an Index Scan. As soon as I make this a range query ("select * from
kvstore where deviceid = 7 AND locid >= 1410929") Postgres decides to do a a
Bitmap Index Scan followed by a Bitmap Heap Scan.

I am somewhat confused by this behavior, but it is more my curiosity that is
asking than a burning need (as in the first case). If someone could explain
what might happen there, I'd be very happy, though! :)

Thanks in advance for any help you might be able to provide!
Daniel

PS: Sorry about the double-post, I accidentally hit send before :-/