We have carried out a systematic experimental investigation to address the question why thin films of Fe$_3$O$_4$ (magnetite) generally have a very broad Verwey transition with lower transition temperatures as compared to the bulk. We observed using x-ray photoelectron spectroscopy, x-ray diffraction and resistivity measurements that the Verwey transition in thin films is drastically influenced not only by the oxygen stoichiometry but especially also by the substrate-induced microstructure. In particular, we found (1) that the transition temperature, the resistivity jump, and the conductivity gap of fully stoichiometric films greatly depends on the domain size, which increases gradually with increasing film thickness, (2) that the broadness of the transition scales with the width of the domain size distribution, and (3) that the hysteresis width is affected strongly by the presence of antiphase boundaries. Films grown on MgO (001) substrates showed the highest and sharpest transitions, with a 200 nm film having a T$_V$ of 122K, which is close to the bulk value. Films grown on substrates with large lattice constant mismatch revealed very broad transitions, and yet, all films show a transition with a hysteresis behavior, indicating that the transition is still first order rather than higher order. ; Comment: 9 pages, 12 figures