My inbox also has lots of unseen messages, I feel your pain :)
I think you're right - the protocol behavior change you are proposing (to change the behavior of the \Recent flag to be more "persistant") is almost certain to break clients, all the other changes might work, but they require client changes and thus can't be fixed on the server.
No, I don't see how they would require any client changes, assuming client already uses recent-counters. There's only small behavioural change in when recent counts would be dropped, it wouldn't require any specific support.
Also, LIST is very expensive, as is status (for some mailbox formats).
STATUS can be, but LIST? It's specifically said in RFC that list should be very inexpensive and I haven't yet heard of a server where this wouldn't be the case.
The ideal implementation from performance point of view would probably be:
LIST all visible mailboxes every n minutes
- If mailbox is \Marked, it's known to have new messages. Highlight it.
- If mailbox is \Unmarked, it's known not to have new messages. If it's highlighted, remove it.
- otherwise issue STATUS (RECENT), unless it's the active mailbox. Based on the result do like above.
The evil implementation I'm planning to use myself is just to issue STATUS (UNSEEN RECENT) for all mailboxes since I want unseen-counts as well :)
