Lorentz symmetry breaking at very high energies may lead to photon dispersion relations of the form omega^2=k^2+m^2+xi_n k^2(k/M_Pl)^n with new terms suppressed by a power n of the Planck mass M_Pl. We show that first and second order terms of size xi_1 >~ 10^(-14) and xi_2 >~ 10^(-6), respectively, would lead to a photon component in cosmic rays above 10^(19) eV that should already have been detected. Only effects suppressed by at least third order in the Planck scale appear consistent with observations.