I'm assuming that if you are using AGS, you have ESRI support. Reaching out to them could be your best bet, because it could be a couple of things.
However, this could address your issue.
When you expand the message at the top of your post, you should be able to right click one of the layers that has that problem and choose "show data store registration page". It is entirely possible that the path is correct on your end but perhaps the server doesn't see the same path (for example mine accesses a shared folder through the network whereas I access it on my desktop as a mapped network drive). see second screenshot
Click the little icon of the hand pointing at the datasheet (below the + and x) and check to be sure the path that is showing there is what you intended.
I find this to be the problem when it happens to me. Often the network path is incorrect (pointing to an older nonexistent server that we used to use). It somehow resets the Server path to a value that was stored previously (I've had to override it several times) and I don't know how or why that happens (bug?).
This apparently happens when you have upgraded your desktop software (it happened to me today after my first time attempting to publish from 10.4). You could also try starting with a blank mxd (created in your current version) and copying all the layers over as suggested in this very similar question Trouble registering datasets with ArcGIS Server 10.1 before publishing an MXD
If this does not work, I don't know what else could be wrong.

