Cannot empty iCloud trash folder
I found out why this was happening. I have a Windows box which I completely forgot I installed iCloud on. For some reason, that temp folder would not get deleted on the Windows machine, and it was re-uploaded to iCloud every night. That's why it was re-appearing on the other devices.

After deleting the folder from the Windows machine, the issue stopped happening. Case closed.