You can create new addresses all you want.. the way most people are doing this is they generate a new address for the user and display it to them. When payment is received to that address it credits the user. You can just generate a new address for each transaction, like a transaction ID essentially. Link2VOIP automated it all and some others have as well, simply by using the built in JSON-RPC functionality.
Satoshi would have to address the other questions about including messages..