In AEM 6.5, I as "admin" or another user from the Administrators group started a "move" operation for ~200 assets (only a few of them are published). This async job finishes successfully, but all published assets cannot be republished due to missing permissions so Request to Complete Move Operation Workflow gets triggered. After I approve this action, assets get published and everything is fine, but this workflow should not be triggered because I have all needed permissions to republish assets in the destination after moving them. We even have a custom check if a user is allowed to republish from the destination folder so this move operation could not even be started if I didn't have the needed permissions. In short, the admin started the async move operation and then has to approve republish workflow.
Admin is listed as the initiator of both workflow and moving job so I can be sure that he has all needed permissions to publish an asset.
If you are using the actual "admin" user, it's almost impossible that there are any permission-related issues. The concept of the admin-user is fundamental to AEM and in more than a decade of AEM experience I have never seen any authorization issues for the admin user.
For the OOTB "administrators" user group and their members things are slightly different, still quite unlikely to have permission issues as described.
If a user tries to move published assets the behavior depends on the users permissions. While a user may have all the required permissions to perform the actual move operation on the author side, he may still be missing permissions to publish and/or unpublish content. If any of the moved elements are published, AEM performs a couple of operations in the background to keep the content in sync between author and publish instances. A published element that should be moved is actually: 1. unpublished, 2. moved, 3. re-published. If the user executing the move is lacking permissions for any of these steps, a "Request to complete move" operation is triggered in the background (please note: user initiating this workflow is always admin as it is triggered by the system) and a user with sufficient permissions has to complete that workflow. See also this blog post  explaining this behavior. To the user, the move operation may still be signaled as "successfully completed" (not sure about the actual wording of the message here, but IMO it is prone to misinterpretion).
My advice is:
Double check on the actual behavior that you are seeing. My feeling is that you are misinterpreting the visible results a bit.
Once you have a clear view on what actually happens at what step, double check on the permissions of the executing users. Make sure that the according group has permissions to publish and unpublish in addition to move rights.
I'm quite sure that the root cause of the issue is with your content editors (the user executing the initial move) permissions.