sort = mailbox-order not unsorted

Ubuntu version: 19.04
Mutt version: 1.10.1-2

I use mutt to read mails from an IMAP server.

My .muttrc contains two lines that I assume to be relevant for this bug:

set header_cache = '~/.muttcache'
set sort = mailbox_order

Expected behaviour:

My mailbox should be unsorted (i.e. all messages appear in the same order as provided by the IMAP fetch 1:* command).

Observed behaviour:

Messages that are already cached (part of the header cache file) are sorted in two groups:

1. all messages without the Deleted flag
2. all messages with the Deleted flag

New messages (not part of the cache file) appear at the bottom (after the deleted messages), so there's a block of deleted messages between the last cached not deleted message and the first new message.

When I delete the header cache file (or disable header caching) before starting mutt everything works as expected (mails are unsorted).