Another approach not yet mentioned is to attempt to extract a 'thin' basis from a given basis. This is along the lines of the stronger form of the Erdos-Turan conjecture, due to Erdos:
If $A \subset \mathbb{N}$ is an additive basis (of order 2), then $\displaystyle \limsup_{n \rightarrow \infty} r_A(n)/\log(n) > 0$. In essence, that a 'thin' basis that Erdos gave using probabilistic arguments is as thin as possible (in a 1956 paper, Erdos proved the existence of bases $A$ with the property that $r_A(n) = \Theta(\log(n))$, thus answering an old question of Sidon). Thus a natural question to ask is whether for a given basis $B$ does there exist a sub-basis $A$ such that $r_A(n) = O(\log(n))$. This question has been answered positively for Waring bases by Van Vu, see http://www.math.rutgers.edu/~vanvu/papers/numbertheory/thinwaring.pdf
On the other hand, his methods rely heavily on the number theoretic properties of the Waring bases and the probabilistic method. It would take a major advance in machinery to prove a similar theorem for arbitrary additive bases. Nonetheless, it is an idea.
Edit: One may also check out Trevor Wooley's 2003 paper "On Vu's thin basis theorem in Waring's problem" for an improvement of Vu's result.