Site-disordered crystals, in which several elements partially occupy the same atomic site, cannot be simulated atomistically without first resolving an explicit ordering, and the number of possible orderings grows combinatorially with supercell size. Because each candidate requires an expensive structural relaxation, locating the global-minimum ordering is a costly combinatorial search. Here, we present an agentic search in which a surrogate model, fitted to previously evaluated configurations, selects each subsequent candidate by balancing exploitation, uncertainty, and novelty. Four surrogates are implemented within a shared framework: an ExtraTrees ensemble, Bayesian ridge regression, sparse ARD regression, and an ALiEGNN-inspired graph ensemble. These are benchmarked against three traditional methods: random walk, Markov chain Monte Carlo, and a genetic algorithm across 14 test cases spanning 12 crystal structures, with exhaustively enumerated global minima as ground truth. The agentic surrogates reach the global minimum in 94% of runs, compared with 55% for the traditional methods, with a median 4.3-fold reduction in evaluations relative to the best traditional method. Bayesian ridge regression succeeds in all runs with the fewest evaluations. Applied to Na2/3FePO4, with coupled Na/vacancy configurational disorder and Fe2+/Fe3+ charge disorder, the framework recovers the experimentally reported ordering when charge states are encoded in the surrogate representation, demonstrating its extension to multi-sublattice disorder.