There are a few things that I have seen that messed with my map services.
1) making sure all permissions were set the same (mostly meaning making sure they are all public).
2) making sure my actual path of my data is set the way you mentioned (web server/arcgis/rest/etc.) and not to a local server host. Sometimes my data got published funky and I could view my web maps fine since I was on the same network but no one else could (like a story map).
3) Make sure you can view this web map on another computer with possibly an outside connection (like, not on your local server).