I'm familiar with this problem. The simplest workaround is to conditionally repeat the operation. I've never seen it fail twice in a row - unless there actually is an open file or a permissions issue, obviously!
rd /s /q c:\deleteme
if exist c:\deleteme rd /s /q c:\deleteme