List the directories deeply-nested-first.
find . -depth -type d -exec rmdir {} \; 2>/dev/null
(Note that the redirection applies to the find command as a whole, not just to rmdir. Redirecting only for rmdir would cause a significant slowdown as you'd need to invoke an intermediate shell.)
You can avoid running rmdir on non-empty directories by passing the -empty predicate to find. GNU find tests the directory when it's about to run the command, so directories that have just been emptied will be picked up.
find . -depth -type d -empty -exec rmdir {} \;
Another way to speed up would be to group the rmdir invocations. Both are likely to be noticeably faster than the original, especially under Cygwin. I don't expect much difference between these two.
find . -depth -type d -print0 | xargs -0 rmdir 2>/dev/null
find . -depth -type d -exec rmdir {} + 2>/dev/null
Which method is faster depends on how many non-empty directories you have. You can't combine -empty with methods for grouping invocations, because then the directories that only contain empty directories aren't empty by the time find looks at them.
Another method would be to run multiple passes. Whether this is faster depends on a lot of things, including whether the whole directory hierarchy can remain in the disk cache between find runs.
while [ -n "$(find . -depth -type d -empty -print -exec rmdir {} +)" ]; do :; done
Alternatively, use zsh. The glob qualifier F matches non-empty directories, so /^F matches empty directories. Directories that only contain empty directories can't be matched so easily.
while rmdir **/*(/N^F); do :; done
(This terminates when rmdir receives an empty command line.)