it doesn't take a huge hit listing e.g. 4k files in a directory anymore.
Umm, maildirs store each message in its own file. I clean up (archive) emails from each past year in a separate folder and still easily have 8k files in each... and that is not my busiest mailbox.
After a few thousand items of anything, the proper tool for the job is a database, not a file system. Though file system can be described as a kind of database, any in case there are problems common to both, such as fragmentation, a specialized data storage always beats generic ones. Personally, I like what Dovecot does - maintains a mbox-like structure ("old-fashined", all messages from a single mail folder in a single file) which is also padded appropriately so fields can be updated without rewriting the file) and builds an index file on top of it to enable efficient random message access. In this way you get efficient, big, append-only data files, and small, easily cacheable index files: win-win.