Please we aware that ESRI's latest documentation on how to deploy third-party Python packages with ArcGISServer omits a very important step. In order to create a clone that ArcGIS Server will have access to, you need to make sure that the clone is created under the ArcGIS Server account. This bit is specified in earlier documentation (for example, see the documentation for 11.1) but seems to have been removed starting at 11.2.
I only wanted to mention it here to hopefully save someone else from having to go through a bunch of unnecessary troubleshooting. After a week+ of testing we reached out to ESRI tech support and they had us create a clone under the ArcGIS Server account which fixed our issue. It was confirmed by the ESRI analyst that this is still a requirement (we are running Server 11.3) despite the fact that is not mentioned in the current documentation.
I have reached out to ESRI through the Feedback link and suggested they update the documentation as well.