What is the most scalable way to add new users in
postfix? I don't necessarily want to create a new user in
/etc/shadow just for email. I know I can use aliases but this does not solve the issue of creating an entirely new user that has email.
Youre looking to set up a postfix virtual server. This is extremely common, and if you google 'postfix virtual server' plus your distribution name, you'll likely come up with a guide.
But if you want to figure out everything yourself, the setting you want to start with is virtual_mailbox_maps.
Here's a detailed tutorial to help you setup a mail server on Debian. It stores mail accounts in MySQL database, so that you don't need to create unix accounts anymore. http://workaround.org/ispmail