If it's all IMAP, then yes, that's how it should work.
I have three clients connecting to my own IMAP server and it works just as you described. You might want to check that all accesses to your mailbox are indeed via IMAP.
'Marked Read' is an IMAP attribute, yes. In actuality, it's not quite that simple because there's another flag that the server uses to show that no client has seen this email and they interact a little but. However, the interaction is documented in the RFC and it's not hard for clients to get it right.
Wade.
"Insert crowbar. Apply force."