If they create a new version of a deleted file, why wouldn't that just be treated as an entirely new file? If the rm trashcan altered the filename (like, say, appending the time stamp of deletion) upon "deletion", that would avoid name collisions. Or just do like OS X and append -0, -1, etc.
