According to the Help you can use a Synchronize command with IMAP
accounts. Have you tried doing that?

Yes, the inbox folder is set to synchronize on send/receive.

It may help if you explained more how you download messages,
e.g. just via Send/Receive?

Yes, I download messages using send/receive. After I read a message (and
mark it as read), on the next send/receive the message becomes unread and I
get the new mail notification.

Also, you could use the troubleshooting log
for IMAP to see if OE is doing what you think it should be doing.
If so, you may have evidence that the source of your symptom is really
in your server and in that case ask your server operator to make changes
so that OE's requests are honored. Etc.

I have a few pieces of evidence that this is an OE problem. The first clue
is that other clients, including Outlook and Thunderbird, do not have the
problem with the same server. Another clue is from Princeton's website:

"Some e-mail clients set message flags improperly. Outlook Express 5 in IMAP
mode does not update message flags (Read, Deleted, etc.) on the server until
the program exits. Users of Outlook Express (any version) using IMAP may see
read messages revert back to an unread state. This is due to Outlook Express
incorrectly using multiple connections to the same mailbox. This is a
documented bug with Outlook Express in IMAP mode."
(http://helpdesk.princeton.edu/kb/display.plx?ID=3542)

I don't go to Princeton or use their server by the way, I just found this
with a web search.

I took a look at the logs but they don't mean anything to me.