8.1 -- very slow query time because of "BETWEEN" (dbmail)

Here is the original query which runs over 2500 ms:

SELECT message_idnr,headername,headervalue
    FROM dbmail_headervalue v JOIN dbmail_messages m ON v.physmessage_id=m.physmessage_id
    JOIN dbmail_headername n ON v.headername_id=n.id
    WHERE m.mailbox_idnr = 417 AND message_idnr BETWEEN 253775 AND 253775 AND lower(headername)
    IN ('from','to','cc','subject','date','message-id','priority','x-priority','references','newsgroups','in-reply-to','content-type');


The strange part is that if you change the "BETWEEN" to just an "= 253775" . . . the query takes around 70ms.

Running
select * from dbmail_messages
    where (mailbox_idnr = 417)
    AND message_idnr > 253755 AND message_idnr <= 253790

takes 20ms and the same when it says "BETWEEN"


Is my answer to just upgrade to 8.2 ?  Is this a known problem in 8.1 ?