In the beta-deformed N=4 supersymmetric SU(N) Yang-Mills theory we study the class of operators O_J = Tr(Phi_i^J Phi_k), i eq k and compute their exact anomalous dimensions for N,Jtoinfty. This leads to a prediction for the masses of the corresponding states in the dual string theory sector. We test the exact formula perturbatively up to two loops. The consistency of the perturbative calculation with the exact result indicates that in the planar limit the one--loop condition g^2=hbar{h} for superconformal invariance is indeed sufficient to insure the {em exact} superconformal invariance of the theory. We present a direct proof of this point in perturbation theory. The O_J sector of this theory shares many similarities with the BMN sector of the N=4 theory in the large R--charge limit.