There may be something you can do with Maplex, but I don't know it well enough to give you any pointers there. As an alternative you might look into custom overlay grids (check the Desktop Help for more info). Basically, these are like grids and graticules, but are based on feature layers. One example I have used is a time zones feature layer with the custom overlay grid set to label each zone around the edge of the data frame. If the feature layer is line data the grid will center the labels on the lines around the edge of the frame. If the feature layer is polygon data the grid will center the labels on the polygon around the edge of the frame. Maybe worth looking into?
