As soon as the unlink action starts, the file is no more visible in the file system and you can even have a new file with exactly the same name from that point.
Actually, that's only the case AFTER unlink returns, not while it's running.
So IMHO there is no need to rename the file, just start the unlinking in a separate thread. I can see a source of race conditions there, though, need to be careful.
Starting a thread for each delete call is simply a bad idea, I guess you'll agree. So what remains is to have a single thread do all the delete calls on your behalf, but that leads to files remaining visible for several seconds if you remove a dozen or so. The solution to that is to rename the file first, and then add it to the thread's queue, and this is exactly what it does now.
What we SHOULD do is make the "slow delete" function no longer the default. Maybe remove it alltogether, as even the old boxes will already have evolved to ext4.
Note that normal users never see this, the GUI implements "delete" as "move to trash". It's the trashcan purging that will actually delete them.