We have employed multimolecular beam techniques to study the transient and steady-state kinetics of the CO oxidation on alumina-supported Pd model catalysts as a function of particle size and surface structure. The model systems were prepared under UHV conditions on a well-ordered alumina film on NiAl(110) and were previously characterized with respect to their geometric and electronic structure and their morphology. Crossing two molecular beams on the sample surface we have systematically probed the CO2 production rate over a wide range of reactant fluxes and at different sample temperatures. Characteristic differences as a function of particles size are observed in both the transient and steady-state regime. In order to relate these effects to the differences in structure and adsorption properties, we have performed microkinetic simulations of the entire series of transient experiments. Whereas it is found that the kinetics on large and ordered Pd particles can in general be described by a homogeneous surface model, significant deviations remain with respect to the kinetics on small and defect-rich particles. In order to semiquantitatively simulate these effects, we consider a heterogeneous surface model, which takes into account the simultaneous presence of different types of adsorption sites. Depending on their distribution, surface diffusion between these sites is included. It turns out that the differences observed for the small particles can be qualitatively understood by a simple model, where we add a small fraction of weakly CO binding sites to the regular adsorption properties. This type of modified adsorption behavior is in agreement with previous desorption studies.