May I suggest that the specific details of this be left to the
implementation effort. What is easy to implement in this area depends
significantly on what platform (and here I mean more imap libraries and
imap server technology than say python vs ruby vs .net vs C) A simple
requirement like the implementation should consider how to handle abuse
of message marking.