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 ?