When creating a cached map, the extent of tiles built will be based on the full extent that you have set in the MXD.  Partial tiles will not be created.  This means that even if you set the top cache scale at 1:1 million, it will not necessarily create tiles for your entire visible map (in the MXD) at 1:1 million.  By this I mean that the tiles around the perimeter may get cut off.  For example, full tiles will be built starting from the middle of the map.  When you get to the edge of the map, the full extent specified in the MXD may run down the middle of a tile.  This tile will not be created, as it is "incomplete".  This is why it may appear that some tiles are missing or have been cut off at full extent in the viewer.

One solution I have found is to set the MXD full extent wider than the extent of all data in the MXD (this is the default full extent).  Create the cache tiles at whatever your desired scales are.  When the tiles are finished, you can then go back to your MXD and set the full extent to your desired full extent (the extent that is used by the "full extent" button on the site).