I think your approach would work, however, if I set
up aliases similar to:

@barbaz.mydomain.com -> barbaz@mydomain.com.

I believe I can do that in postfix with some regex magic.

Yes, that would work perfectly without any regex.
You just point the catchall alias to the "user".
@barbaz.mydomain.com -> barbaz@mydomain.com



one stumbling block could be that we don't
know the various subdomains ahead of time.

The subdomain can be any value that the user
wants, and we don't want them to have to
precreate them before they can use an address

Best to my knowledge this is not possible with postfix. But ask the 
postfix mailing list to get a definitive answer. In postfix you have to 
tell it the domains it accepts mail for, anything else it considers 
relaying. Otherwise how does postfix know that email is meant to be 
saved here or it is just passing through and you want postfix to query 
DNS to find out where it goes (if relaying is even allowed).



The purpose of the system is that users can create disposable/temporary 
email addresses for various testing jobs.

Are you aware of postfix recipient_delimiter? It allows for disposable / 
wild card addresses. If enabled in postfix, you setup a mailbox user 
like barbaz@mydomain.com and any address with that user and the 
delimiter would still get delivered to that user.

    barbaz@mydomain.com -> barbaz@mydomain.com
    barbaz+randomtext@mydomain.com -> barbaz@mydomain.com
    barbaz+test1@mydomain.com -> barbaz@mydomain.com

You can change the + to any symbol you want postfix to look out for.



I think my "creating users" was me wanting to make sure that when 
postfix
passes an email for "barbaz@mydomain.com" to Dovecot, then Dovecot will 
store it and wait for
someone to come along and impersonate barbaz. i.e. "barbaz" doesn't 
have to exist as a user
already before Dovecot will store the mail.

If you are using LMTP dovecot will only accept emails from postfix that 
it can lookup the /directory/path to from one of the userdb{} or 
passdb{} sections. If dovecot can not find a match in any of the 
userdb{} or passdb{} it will reject the email as user unknown causing 
postfix to send a undeliverable notice email back to the envelope sender 
address, also known as back-scatter. I am not aware of a way to use 
wildcard addresses in dovecot userdb{}, i don't think its possible but i 
don't know what i don't know.