Just updating this thread for the benefit of anyone reading:
Well just as expected, when I picked a VPS and tried to reproduce the issue on purpose, the folders deleted just fine. In fact, I just spot-tested it on 4 different servers and they all deleted folders properly. I'll start to pay closer attention to the details surrounding the issue now. So far I can say:
- It happens on a brand new setup even before any software is installed
- It also happens after all the Windows updates are installed
- It has happened on every one of the 12 VPS's I've set up so far (plus the 2 that I set up for a buddy today)
- It usually happens on folders regardless of their content, but I have also had "File Access Denied" error when deleting text files (same symptom: after attempting to delete the file, wait 60 seconds, hit Try Again, and then it works), but not nearly as often. It's normally folders.
- I'm not running any software (like antivirus) that would scan/do actions on the folders
It was happening all the time, with almost every folder I tried to delete.. but if I can't re-produce the issue now, there's obviously nothing you can do. I'll just keep an eye on it and update the ticket if I have any concrete way of reproducing the issue.
If an issue is found/resolved I'll update the thread again too, but apparently I need to collect more data first.

Scott Wang