The desktop client should report an error message directly the user to clear their cache as the map cache has changed since the last local cache was generated, maybe with a dialog to clear the cache.
This issue came up during the Creating Effective Web Apps class. Here is the note given to students:
Attempting to preview the Portland_Basemap in ArcCatalog Window give the message that the service cannot be previewed. The results from the fact that the ArcGIS Desktop cache is out of sync with the service.
ArcMap from the menus: Customize --> ArcMap Options --> Display Cache --> Clear Cache