So the same danger does exist, but in far fewer situations instead of possibly every move/rename situation that would happen if you delete first?
I know you're dealing with an insane number of files, but this all makes me think of how Dropbox does deduplication (I think that's the right term). If I move a file, it's not deleted and recopied on the server. I assume though that a local system like that would require a much larger destination drive which would negate the problems I'm having anyway.