I am having a similar issue. I'm using the Shaded Relief basemap from ArcGIS Online within Arc 10 at a map scale of 1:11,000,000. The topography resolution appears fine at that scale but the water features of that basemap are noticeably blurry, even when printing on a letter sized piece of paper. Does anyone know how to force the display of a basemap to a higher resolution, such as it appears when you zoom in to the data on the basemap image?