A search for double-heavy tetraquark state candidates Xcc (x) over bar(s) over bar decaying to Ds+Ds+ and D-s*+D-s(*)+ is presented for the first time using the data samples of 102 x 106 Gamma and 158 x 10(6) Gamma(2S) events, and the data samples at root s = 10.52, 10.58, and 10.867 GeV corresponding to integrated luminosities of 89.5, 711.0, and 121.4 fb(-1), respectively, accumulated with the Belle detector at the KEKB asymmetric energy electron-positron collider. The invariant-mass spectra of the Ds+Ds+ and Ds*+Ds*+ are studied to search for possible resonances. No significant signals are observed, and the 90% confidence level upper limits on the product branching fractions [B(Gamma(1S, 2S) -> X-cc (x) over bar(s) over bar + anything) x B(X-cc (x) over bar(s) over bar Ds+Ds+(Ds*+Ds*+))] Gamma(1S, 2S) inclusive decays and the product values of Born cross section and branching fraction [sigma(e(+)e(-) -> Xcc (x) over bar(s) over bar + anythin) x B(Xcc (x) over bar(s) over bar -> Ds+Ds+(Ds*+Ds*+))] in e(+)e(-) collisions at root s = 10.52, 10.58, and 10.867 GeV under different assumptions of Xcc (x) over bar(s) over bar masses and widths are obtained.