I’m going to say it again – Stop deleting media files! Just put that idea completely out of your mind. You’re not going to be able to do that again until you get well-clear of this error.
You can also stop logging in/out.
For now, just keep syncing as normal. Let the devices download the unused files and don’t worry about them. You can run check media on both devices (and check database wouldn’t hurt again either) as much as you want, but don’t delete unused media.
I can’t tell you exactly what it’s going to take to make the error stop, because it should have stopped by now. But you’re going to have to stop deleting media files to let that happen.