I have a similar problem seemingly caused by SP5 update to ARCGIS Server 10.0. I had .mxd published and being used through the rest endpoint. When I installed SP5, all of my Restful services disappeared. There is nothing listed under the cache in IIS. It appears the updated to SP5 removed the web.config file for the rest and soap services. Does anyone know how I can replace those? I have considered do a web server post install again; however this is a production system, and if the post install goes poorly (as is sometimes the case), I could be without critical services. The map service itself is still working and in use by many, but other systems taking advantage of the rest endpoint, no longer have a map background.