I have always found that there are very small practical limits of tiles when using Mosaic. I have much more success by merging strips (or a box) of tiles, then merge the strips, then merge the final set. It all sounds a bit messy, so that is why I script the process, and it helps if the tile names have a pattern. Max count < 10 at a time. In the end I have a grid of 300 tiles that performs surprisingly well.
For more a more general approach to the "13 hours" I use these strategies:
Apply the "Cup of Coffee Rule". If a single process has not completed in the time to have a cup of coffee, then interrupt the process and find a better way.
That might be a different tool, or different software even...
I find that nothing of interest results leaving processes running too long, they are corrupt or incomplete because the system has run out of memory, disk space or otherwise and is useless.
My suggestions are: Make sure your PC is tuned: plenty of local disk space, defragged, and a temp workspace defined as a file geodatabase (the default in ArcGIS 10). This ensures you have enough space for temporary files that are really large in raster processing.
Do some calculations on the 'processing effort' if you can. Esri staff suggest you try a sample first, but that does not really tell you if the process will scale for larger sets. So maybe just tile the data and do it in pieces if a small part works in "Coffee Time".
Have a close look at your data. Unexpected data is often the problem, conflicting projections, null values, missmatch of cell sizes, default tolerances, and many more. Check vectors are clean, and that you have all indexes set, use file geodatabases, not shapefiles. Make sure you do not have single large polygons covering the area that you are using for processing. Dice them up, there is a new tool for that.
For mosaic, just calculate how large the target tile will be with 133 tiles and multiply up to see how much memory that will take uncompressed. Probably more than Amazon's servers.
Basically ArcGIS will not warn you are attempting something impossible, so you have to be wary.