It's NumOfMessages, not NumOfUsers, and Messages = Messages/User * Users. Then the question is whether Messages/User and Recipients/Message remain constant as NumOfUsers goes up. If both do, then your total cost is linear with the number of users, which is what you want. But if either of them is linear in the number of users, then the total number of messages becomes quadratic in the number of users: a linear factor from growth in userbase, and a linear factor factor from increased usage by each user. Most likely there's a logarithmic correlation (Recipients/Message goes up as more people are on the service, but not by as much as total users), which is still generally fine for scalability concerns.
E-mail's actually a really great example. It worked great as long as it was used for person-to-person communication, which held both the number of messages/user and the number of recipients/message constant. Then spammers found out that the more people who had e-mail, the more they could send to at once, and sent recipients/message through the roof. In 1997/98, there were actually a number of articles about how the e-mail architecture was in serious trouble, and unless some way could be found to limit spam, it would collapse within a couple years. Of course, they dealt with it through spam filters and blacklists on the server, so now e-mail works fine.
Twitter's problem is that both Messages/User and Recipients/Message average significantly higher than e-mail, and yet the resources they have available are significantly lower than the full resources of the Internet. So even if they don't have an architectural scalability problem, they could very well have an economics problem.