The problem may be, that the size of blockchain - O(n^2) - determines the complexity of transaction validation, so some naive implementation either require O(n^2) of fast memory, or slow search through the blockchain. Then, if the amount of transactions is O(n^2) and the blockchain size is O(n^2) too, it may end in something nasty as O(n^4) time complexity.
And, yes, I know about hashing, patricia trees, etc. But I point out that the storage is just one piece of rather complex build.
The transaction fee is in place to prevent exactly the O(n^2) worst case scenario I think. For any real usage of the network you are not going to send transactions to everyone in the world. And even if no fee is charged you definitely won't go to O(n^2) transactions/block where n is the world population, there will only be 2.1*10^16 satoshis ever in existence, which is much smaller than 10^20.
