1-Enable Remote staging for a site.
2-In staging server, add a document (for example, a PDF).
3-Wait until preview is created (not sure if this step is needed to reproduce the issue).
4-Move document to Recycle bin.
5-Add another document.
6-Publish to Live. An error appears ("The publication process did not start due to validation errors").
7-Try to publish again. Now it is marked as "Success", but document doesn't exist in remote server.
After removing documents (and existent documents in Recycle Bin), and publishing, and then re-adding document, the document publish fine.