You should look into Postini's SmartCreate option. When enabled, users will be automatically created if they receive three messages in a two week period. Until that time they're unable to access the Message Center, but those three messages will appear in their archive once their account exists.
The advantage of SmartCreate is that you don't have to create users in both your mail system and in Postini, which can mean not having to figure out how to programatically provision users. The disadvantage is that Postini cannot reject mail for non-existent addresses immediately, as it doesn't know if they exist or not.
For us it works well as we've implemented Postini in a non-standard way by putting it behind our corporate mail routing infrastructure which already rejects mail to non-existent addresses. If I was putting Postini on the border as is recommended I'd be programatically provisioning users. For our scenario SmartCreate is more convenient.