We present rigorous performance bounds for the optimal dynamical decoupling pulse sequence protecting a quantum bit (qubit) against pure dephasing. Our bounds apply under the assumption of instantaneous pulses and of bounded perturbing environment and qubit-environment Hamiltonians. We show that if the total sequence time is fixed the optimal sequence can be used to make the distance between the protected and unperturbed qubit states arbitrarily small in the number of applied pulses. If, on the other hand, the minimum pulse interval is fixed and the total sequence time is allowed to scale with the number of pulses, then longer sequences need not always be advantageous. The rigorous bound may serve as testbed for approximate treatments of optimal decoupling in bounded models of decoherence.