Does anybody know how on earth Bitcoin is supposed to scale in X years, when everyone needs to have every transaction ever made stored on their computer?
It's an implementation detail. Currently the reference wallet stores all transactions, but future versions will be able to prune old blocks and rely on more recent "reference blocks" as their starting point.