Elementary gas-surface processes are essential steps in heterogeneous catalysis. A predictive understanding of catalytic mechanisms remains challenging due largely to difficulties in accurately characterizing the kinetics of such steps. Experimentally, thermal rates for elementary surface reactions can now be measured using a novel velocity imaging technique, providing a stringent testing ground for ab initio rate theories. Here, we propose to combine ring polymer molecular dynamics (RPMD) rate theory with state-of-the-art first-principles-determined neural network potential to calculate surface reaction rates. Taking NO desorption from Pd(111) as an example, we show that the harmonic approximation and the neglect of lattice motion in the commonly-used transition state theory overestimates and underestimates the entropy change during the desorption process, respectively, leading to opposite errors in rate coefficient predictions and artificial error cancellations. Including anharmonicity and lattice motion, our results reveal a generally neglected surface entropy change due to significant local structural change during desorption and obtain the right answer for the right reasons. Although quantum effects are found to be less important in this system, the proposed approach establishes a more reliable theoretical benchmark for accurately predicting the kinetics of elementary gas-surface processes.