Jay,
You have quite a bit of overlap in the images. Have you tried increasing the Shrink parameter when building footprints? You should be able to shrink somewhat excessivley because of the amount of overlap. It will be better than manually editing, which you can do using the tips above.
The mosaic dataset is the approach to take for resolving the image collars, but to serve it you must have the Image Extension regardless of whether you make an image service from the MD or if you make a map service with the MD in it. Without the extension you are going to have to create a flat file on disk of the whole thing (a raster dataset), then publish that. Basically, you run Copy Raster or Export Data from the UI, and input the mosaic dataset.
Regards,
Eric