Configuration
There could be global and user-specific configuration files, similar to how ACLs work. I think the global virtual mailboxes should be only defaults though, so that users could delete them and create a new mailbox (virtual or non-virtual) with the same name.
The global virtual mailboxes could be described in a single file, such as:
Trash deleted
Work/My Unseen (mailboxes "box1" "box2" "box2/*") or to "tss@iki.fi" to "timo.sirainen@iki.fi" unseen
So the format would be <virtual mailbox name> LF
Per-user virtual mailboxes could also be listed in a similar file. If the search condition is empty, a globally defined virtual mailbox has been deleted.
Another way would be to have per-mailbox dovecot-virtual files, but I'm not sure how global virtual mailboxes could then be easily deleted. Also having all of them in a single file makes listing the mailboxes pretty fast.
The search condition would be a standard IMAP SEARCH reply, with the exception of the mailboxes parameter to specify what mailboxes are used.
Virtual mailboxes would be implemented as a new mail storage backend, so their namespace configuration would be like:
namespace private { prefix = "virtual/" location = virtual:~/virtual:GLOBAL=/etc/dovecot/virtual-globals.conf }
Syncing
~/virtual directory would contain index files for the virtual mailboxes. If the index files don't exist, a full resync for the virtual mailbox is done. This means opening all the real mailboxes configured for the vbox, running the SEARCH command and adding the returned UIDs to the vbox's indexes.
The index would contain at least mailbox ID and message UID numbers. Probably would be a good idea to also save UIDVALIDITY numbers just to be safe, although that's a bit of a waste of space and it could be handled in other ways too, such as changing the mailbox ID whenever its UIDVALIDITY changes..
Mailbox IDs would be mapped to names in mailbox list index. This index already exists, although there still seems to be some bugs in it. At least creating a new list index has a race condition. I should look into making the list index a bit more realiable. Also the list indexes work only with Maildir++ layout currently.
After the vbox has initially been synced, it needs to also handle updates. I think optionally the updates could be done the same way as full sync (opening all mailboxes to see if there are changes), but a faster way would be to update the virtual mailboxes immediately when the real mailboxes are being modified.
So IMAP, POP3 and deliver all need to be aware of the virtual mailboxes and what real mailboxes are mapped to what virtual ones. Whenever doing a change that causes the message to either be added to or removed from a virtual mailbox according to their rules, the virtual mailbox's index is updated immediately. Being able to determine this change quickly might be the biggest change required to Dovecot's base code.
Changes
Virtual mailboxes would share their state with the real mailbox, so any flag changes done in the vbox would be immediately changed in the real mailbox as well. The same goes for expunges.
Virtual mailboxes' transaction logs would use different records for expunges and removals. Expunges would be handled normally, but removals wouldn't be removed from the in-memory view of the mailbox until EXPUNGE command was given (although they would be removed from dovecot.index immediately, so new sessions wouldn't see them). This makes it possible to have a vbox with only unseen messages, but without the message getting expunged immediately after a client opens the mail. So the EXPUNGE command could act as a "session synchronization" command. And of course it would also expunge the messages that had been marked as \Deleted.