Reproduced on version 1.3 on RHEL5.
Tested on RHEL5/4 x i386/x86_64 with
python-qpid-0.7.946106-14
qpid-cpp-client-0.7.946106-19
qpid-cpp-client-devel-0.7.946106-19
qpid-cpp-client-devel-docs-0.7.946106-19
qpid-cpp-client-ssl-0.7.946106-19
qpid-cpp-server-0.7.946106-19
qpid-cpp-server-devel-0.7.946106-19
qpid-cpp-server-ssl-0.7.946106-19
qpid-cpp-server-store-0.7.946106-19
qpid-cpp-server-xml-0.7.946106-19
qpid-java-client-0.7.946106-12
qpid-java-common-0.7.946106-12
qpid-java-example-0.7.946106-12
qpid-tools-0.7.946106-11
qmf-devel-0.7.946106-19
python-qmf-0.7.946106-14
qmf-0.7.946106-19

and it works -->VERIFIED

reproducer:
import sys
import os
from qpid.messaging import *
import qmf.console
import time

if len(sys.argv)<2:
  broker =  "localhost:5672"
else:
  broker = sys.argv[1]

if len(sys.argv)<3:
  address = "amq.topic"
else:
  address = sys.argv[2]

connection = Connection(broker)

try:
  connection.open()
  session = connection.session()

  snd = session.sender("tmr; {create:always, node:{type:queue, durable:True}}")
  rcv = session.receiver("tmr; {create:always, node:{type:queue, durable:True}}")
  m1 = Message("test_message_reject", durable=True, correlation_id="Msg00010")
  snd.send(m1)
  m2 = rcv.fetch()
  session.acknowledge(message=m2, disposition=Disposition(REJECTED))
  connection.close()

  os.system("service qpidd restart")
  time.sleep(20)

  session2 = qmf.console.Session()
  broker = session2.addBroker()
  agent = None;
  for i_agent in session2.getAgents():
    if i_agent.getAgentBank() == '0':
      agent = i_agent;
  queue_list = session2.getObjects(_class="queue", _agent=agent)
  for queue in queue_list:
    if queue.name == "tmr":
      print "queue depth:", queue.msgDepth
      assert queue.msgDepth == 0

  session2.delBroker(broker)

except MessagingError,m:
  print m

An advisory has been issued which should help the problem
described in this bug report. This report is therefore being
closed with a resolution of ERRATA. For more information
on therefore solution and/or where to find the updated files,
please follow the link below. You may reopen this bug report
if the solution does not work for you.

http://rhn.redhat.com/errata/RHSA-2010-0922.html

    Technical note added. If any revisions are required, please edit the "Technical Notes" field
    accordingly. All revisions will be proofread by the Engineering Content Services team.
    
    New Contents:
A flaw in the message broker caused rejected messages to remain on the queue. If a durable message was rejected and the broker was restarted, the message would stay in the queue since it was not removed from the durable store. As a result, the rejected message was erroneously redelivered. With this update, the aforementioned defect has been fixed and rejected messages are now properly dequeued.