Even if every user had dozens of queued up messages, I don't think it equals millions in storage costs. Maybe I'm naive, but I have a storage/database/queue with billions of records and it costs <$700/month.
>>mortal+(OP)
I think some messages will cost more storage than others. I have 4 devices synced to my Signal account. Yesterday, my friend sent me a 6.8 MB cat video[1]. I presume Signal has to store this cat video until I boot up my 4th device and load the queued messages.