The answer is not known, but many believe it is: "Yes, every CFT has an AdS dual." However, whether the AdS dual is weakly-coupled and has low curvature -- in other words whether it's easy to do calculations with it -- is a different question entirely. We expect, based on well-understood examples (like $\mathcal N=4$ SYM dual to Type IIB strings on $\mathrm{AdS}_5 \times S^5$), that the following is true:
- For the AdS dual to be weakly-coupled, the CFT must have a large gauge group.
- For the AdS curvature scale to be small (so that effective field theory is a good approximation), the CFT must be strongly-coupled. In well-understood examples, the CFT has an exactly marginal coupling which when taken to infinity decouples stringy states from the bulk spectrum. By contrast, at weak CFT coupling, the AdS dual description would involve an infinite number of fields and standard EFT methods would not apply. (This doesn't necessarily mean calculations are impossible: we would just need to better understand string theories in AdS -- something which is actively being worked on.)
As far as I know, appropriate conditions for CFTs without exactly marginal couplings to have good AdS EFTs are not known. Also, well-understood AdS/CFT dual pairs where the CFT violates one or both of the above conditions are scarce.