If you only ever want to append messages, and never want to mutate or remove them, I would do this scheme in two parts: 1) an append-only message store; 2) a set of indices stored alongside (1). To append thousands of messages per second, I would probably want a system with multiple writers appending to multiple files (mbox) or directories (maildir), and cycling/archiving the mailboxes as they get large.

As for (2), I know a lot less about indexing messages than I do about storing them, but I would try out an off the shelf SQL or noSQL system and measure the performance, before trying to build anything fancy.