Just posted the following in another thread a few days ago, see if it solves your problem:
First, confirm that there is no gap in the source imagery. If at least one raster has a value where the output shows NODATA, it might be a matter of setting parameters in the tool.
The last two optional parameters are Mosaic Operator and Mosaic Colormap Mode. The default for the former is LAST, which gives the output the value of the last source raster that overlaps that cell. If this is NODATA, that will appear in the output. By changing this to MAXIMUM (or whatever suits your data best), NODATA values will be overridden by actual values in the output.
The same idea holds for the Mosaic Colormap Mode, but with options for a colormap instead of cell values.