With our customized PRJ (Atatched .zip, saying our own 'LCC' or 'Ain el Abd 1970 Aramco Lambert 2'), building statistics on mosaic datasets couldn't be successful. Basically, its operation took a week not to finish. However, building statistics on same mosaic dataset with 'WGS84 /geodetic or UTM' can be successfully accomplished in one day (without ArcGIS 10 SP1) or hours (with SP1).
The sources are GeoEye (UTM/WGS84). During Add Rasters, the transformation is (Ain_El_Abd_To_WGS_1984_2).