yes we have the set of UTXOs, but the entire chain must be traversed in order to compute this set! Thus computation issues are built into the system. If you were to have a tx format like OP suggests, you could eliminate much of the computation(to find a balance, you just find the last tx with account X as destination).
Without the current design, you cannot have a zero trust system.
Most efficient designs are of course possible, but decrease trust. SPV is an example.