OK, thanks for the pointer.
I did read the paper, but somehow forgot about it when browsing the dust spam discussion threads, which looked quite depressing. So the huge storage usage is at least not a design bug, but just an implementation issue?
It isn't a bug but even w/ block chain pruning a block chain will always require more resources than a ledger system. Consider it a cost of not having a trusted third party.
Also I wouldn't say it is an implementation issue pruning simply hasn't been implemented. It is also possible to construct lite clients which have no block chain stored and communicate w/ a trusted blockchain server.