Answer
ArcIMS 3.1 offers faster spatial indexes for shapefiles than ArcIMS 3.0. In addition, problems with spatial indexes for shapefiles were fixed at ArcIMS 3.1. If you have any issues displaying a shapefile, first try deleting the spatial index to see if this solves the problem.
Shapefile spatial indexes that were built with ArcIMS 3.0 should be deleted and rebuilt with ArcIMS 3.1. To do this, delete the shapefile .sbn and .sbx files. When you publish a MapService that uses the shapefile, the ArcIMS Spatial Server will generate new spatial index files.