When publishing your map service in the Service Editor, Go to the Caching -> Advanced Settings. Down the page, where you see Area of interest to cache, you can set it to either Full extent of the map (maybe entire world), Current Extent of the map, or you can import the Area of Interest from a Feature Class. If you select the last one, ArcGIS prompts you for the location of the feature class, which could come from an ArcSDE, file geodatabase, or even a shapefile, I believe. The features within define the area over which the tiles are generated. Simply point the Area of Interest to your data, and it will only build over that area.
The help for ArcGIS Server details how to add a "No data present" tile image to your cache after it's generated. Basically, you add a tile image that matches your cache format into the cache. Follow this link for the ArcGIS Server Frequently Asked Questions and search for "missing.png"
Here's a link to ArcGIS's list of best practices. for creating tiled cache that you may find useful.