Maybe the message data can be pruned like every 2 weeks or something. 
Messages are only relevant for a short period of time. Would this be possible?

>By default messages can be kept 24 hours or so and if you want it to stay longer you would pay some fee. And that fee can be calculated depending on size (byte) of that message.

I don't really like the idea of charging a fee for messages. Users do that for free on other sites. 
Why not just prune the data say older than a week or 2?  this means messages will never take much space, even if the number of messages grows a lot we can always reduce period when its stored to a few days.

edit: My bad I didn't read your post properly, yes 24 or maybe 48 hours free and then a fee. I still think though that it will sound a bit weird to ask people money to keep their messages..maybe it should be an option not visible on the interface.