I experienced the same issues as Harry Johnston has mentioned. rmdir /s /q would complain that a directory was not empty even though /s is meant to do the emptying for you! I think it’s a bug in Windows, personally.
My workaround is to del everything in the directory before deleting the directory itself:
del /f /s /q mydir 1>nul
rmdir /s /q mydir
(The 1>nul hides the standard output of del because otherwise, it lists every single file it deletes.)