I don't know if anyone ever followed up, but here is the issue and how to get around it:
Issue: If a raster's extent is beyond the extent of the Mosaic Dataset's coordinate system's extent, it will not be added, and produces the 999999 error.
Workaround: The offending raster needs to have a coordinate system, and then run the Clip tool (Raster toolbox under Data Management) with the Maintain Clipping Extent option checked (it is not by default). You will need to define the extent coordinates to be within the extent of the coordinate system. For example if the raster's right maximum coordinate is 180.000543 and the coordinate system is WGS_1984, which has a limit of 180.0, then you'll need to enter 179.999999 (I tried 180 and it didn't work). The result was the correct number of columns and rows with all the data.
I asked Technical Support to log an enhancement to the Add Raster tool so it gives a useful error message.
What do you do if the data frame required exceeds the extent of the coordinate system? We are using state plane, and are on the border of north and south. The overlap on both sides is insufficient, and I' using the rasters in ArcPad, so the coordinate system must be the same. Can I project into say UTM and and then have the mosaic in SPS if a .sid exceeds the SPS extent?
I got the exact same errors in 10.2.2 where I had loaded a set of imagry and then needed to go back and add more tiles I kept getting the same errors as above. After trying numerous times to Define and Build the Overviews, I compressed the file geodatabase and then reran the Build Overviews by right clicking on the raster mosaic itself it worked.