The elements of $S$ are conjectured to be $\mathbb{Q}$-linearly independent, and so a basis for the $\mathbb{Q}$-linear span of the multiple zeta values. 

This is what Francis Brown accomplished at the motivic level. Actually, his proof via motives goes through the direction that is currently missing on the level of numbers, which is why it doesn't lead to an algorithm for writing down the (conjecturally unique) expression. In Theorem 7.4 of [*Mixed Tate motives over $\mathbb{Z}$* (Ann. Math., 2012)], he proved that the motivic enrichments $\zeta^{\mathbb{m}}(\mathbf{s})$, $\mathbf{s} \in \{2,3\}^{\times}$ of the $\{2,3\}^{\times}$-zeta values are $\mathbb{Q}$-linearly independent. In the motivic formalism, the dimension $d_n$ of the $\mathbb{Q}$-linear span $\mathcal{M}_n$ of the motivic MZV of a given weight $n$ is well known to be equal to the $z^n$ coefficient of $1/(1-z^2-z^3)$, which is also the number of expressions of $n$ as a sum of $\{2,3\}$-elements, and so the number of $\{2,3\}^{\times}$ zeta values of weight $n$. The linear independence of the $\zeta^{\mathbb{m}}(\mathbf{s}), \, \mathbf{s} \in \{2,3\}^{\times}$ then implies the equality: these values form a basis for $\bigoplus_n \mathcal{M}_n$, at the motivic level. There is a realization homomorphism $\mathcal{M} \to \mathbb{R}$ sending $\zeta^{\mathbb{m}}(\mathbf{s}) \to \zeta(\mathbf{s})$, and it follows (non-constructively) that there is a representation at the level of numbers. 

However, proving $\mathbb{Q}$-linear independence remains completely out of reach on the level of numbers. We know very little here: even the irrationality of $\zeta(5)$ has remained an unsolved problem. 

On the level of numbers, what is immediately derived from the motivic formalism is the upper bound $\dim{M_n} \leq d_n$ of the conjectured dimension. This was proved independently by Terasoma and Goncharov; it means that there are many linear relations among MZV of a given (high enough) weight. From this point of view, identities like the weight $12$ one you quote are not surprising. Explicit identities such as this one were obtained by [Gangl, Kaneko and Zagier][1], and are linked to modular forms of weight $n$, via Eisenstein series. 


  [1]: http://www2.math.kyushu-u.ac.jp/~mkaneko/papers/GKZ.pdf