I run into this issue occasionally. Like you mentioned the Maintain Sheet Edges option is supposed to ensure that adjacent footprints aren't modified along their adjoining seams. In the mosaic dataset properties under the default tab be sure to turn on the option to clip mosaic to boundary, but turn off the clip mosaic to footprints option. This is an easy way to ensure that only the extent or outer boundary of your mosaic will be clipped and not the interior of your imagery. Hope this helps!