In fact the more general N-body problem is perhaps one of the most classical uses of high order Taylor methods, in particular for studying the long term stability of the solar system. Here is a paper from 1993:
http://adsabs.harvard.edu/full/1993A%26A...272..687L. Rigorous error analysis of Taylor methods for ODEs goes all the way back to Moore's original work on interval arithmetic in the 1960s; in the early 2000s Makino and Berz developed so-called Taylor models which combine rigorous error bounds with accurate long-term propagation of changes due to perturbations in the initial values (see
http://bt.pa.msu.edu/index_TaylorModels.htm); they used it to study the dynamics of the solar system among other things. R. Barrio and others have published several papers about reliable solution of ODEs using Taylor methods; leading to the development of the TIDES software. See several references listed on
http://cody.unizar.es/tides.html. In particular the paper
https://doi.org/10.1016/j.amc.2004.02.015 from 2005 investigates using variable order Taylor series with extended precision for the solutions of dynamical systems. The paper
http://dx.doi.org/10.1155/2012/716024 from 2012 is specifically about obtaining periodic solutions of dynamical systems using a high order Taylor method with multiple precision arithmetic.
Actually, I made the first comment after I checked the second author's earlier paper https://arxiv.org/abs/1109.0130 where they essentially made the claim about inventing "CNS" as the first-ever reliable technique for long-term solutions of dynamical systems, without referencing any of the earlier work I mentioned above.
However, I just checked the actual text of this new article on the three-body problem (through sci-hub) and there the authors do cite the earlier work I mentioned above, giving proper attribution to others for the basic ideas behind what they call "CNS"! So all is actually well, and the peer review presumably did work (or the authors found out about the earlier work even before writing the new paper). It is just the press release that is misleading, as usual.
To answer your question, I'm not really familiar with the research on the N-body problem, so I can't say why or whether no one tried looking for periodic solutions in this way before. Perhaps no one actually thought of it, or they didn't try since they didn't expect to find anything, or they didn't have the computational resources, or they just couldn't figure out the details of how to do it (which the present authors did, and deserve credit for). Again, I was not trying to downplay the significance of this work, and finding new applications of existing methods (and making even tiny improvements along the way) is how science progresses. It also happens all the time that methods get rediscovered/reinvented independently.