This is a tough one, which is why we mirror the folder structure our published services with a folder of map documents used to publish the services. You can see the location where the original mxd was published from using ArcGIS Server Manager to view the General tab of the service properties. The same thing is also in ArcCatalog service properties but it's on the Parameters tab. However, this won't do any good if the MXD has been moved or deleted since publishing.
Edit:
You might be able to find in your server directory at \arcgisserver\directories\arcgissystem\arcgisinput\ServiceFolderName\ServiceName.MapServer\extracted\v101
ArcGIS Enterprise