[pmjordan]

I suspect you already know about this, but the google apps/domain service lets you add aliases and mailboxes painlessly.

[dkokelley]

I suspect 'on-the-fly' could mean automatically, as in the server generates them as needed. I'm not sure if Google Apps can do that.