From my experience, the checkerboard (I've always called it chessboard :)) look and feel is related to incomplete or incorrectly-created overviews (through no fault of yours). To get around this, I used the Define Overviews GP tool and checked the box for Force Overviews. This option generates overviews for all extents, ignoring raster pyramids of the source data during the process. Try this on a subset of your data that you know has checkerboard issues to verify, but hopefully you'll have good luck with this approach.
Alternatively, there could be a difference in pixel depth among your various input source rasters. Check the pixel depth (e.g., 1-bit, 8-bit, 16-bit, etc.) to see if you have a mixture. I found this to be the case at one point in the past; I ended up forgoing the entire mosaic dataset approach and instead going with an unmanaged raster catalog stored in a file geodatabase. You may need a mosaic dataset for your specific workflows, so this may be irrelevant to you. If you don't, consider using an unmanaged raster catalog published as a map service (from an MXD not an MSD if using 10.0) as a workaround rather than a mosaic dataset as part of a map or image service.
