DEMs are susceptible to artifacting. Many DEMs already have some artifacts introduced during creation; hillshades of those DEMs will magnify the anomalies and make them visible. If the DEM does not have any artifacts before it is rendered as a hillshade, the problem may be caused by using an improper resampling method when projecting the DEM data.
A DEM is continuous raster data. The bilinear resampling method should be used in raster projections or any raster transformations. When projecting raster data using the Project Raster GP tool, do not use the default resampling method. Choose bilinear resampling or cubic convolution resampling method instead.
In ArcGIS 9.0, there is a problem in setting the correct resampling method. Choosing bilinear or cubic resampling will always use default nearest neighbor resampling. This problem has been fixed in 9.1.