Finding message by ID fails when message not visible

[Kai von Fintel]

I'm puzzled by the following behavior: if I search in an nnimap group
for a message with a particular message-ID, the search fails unless the
message is visible. If for example, only new messages are shown, the
search for an old message with a particular ID fails but the same
message is found when "/o" has made the old messages appear.

This is relevant because I use links to gnus messages from org-mode and
more often than not the link fails: I get taken to the nnimap group that
contains the message, but I get the error "No such article (may have
expired or been canceled)", even though the message is in fact in the
group.

I suppose org-gnus.el might have to be amended to work around this, but
first I'd like to understand whether this is expected behavior in gnus.

Can anybody enlighten me or help me trouble-shoot this?

-- Kai.