It is useful to provide some background information first.
When a backup job starts, the following will be performed in order;
1. Run the pre-commands
2. Create Volume Shadow Copy (if needed)
3. Get the file list from offsite servers
4. Compare the local files with the remote file list to determine the files to be uploaded
5. Upload the determined files
6. Run the post-commands after the file upload is completed
7. Remove the created Volume Shadow Copy.
The reason for the message "..filename... has been removed already"
Such message is shown when during the upload stage, the file identified during file comparison stage (4) no longer exists. This usually happens to temporary files that are created and removed frequently. In rare cases, it is due to the fact that the software couldn't access the source files during the upload stage. Possible reasons for this are: corrupt spots on the disk, anti-virus software, or VSS (windows shadow copy) was not able to create a snapshot of it.
To attempt resolution please try (in order):
1. Restarting the Volume Shadow Copy service
2. Running a "CHKDSK /R" on device in concern
3. Checking the event viewer to see if there are any disk, ntfs, vss errors