I'd migrated a huge collection of files from a backup of a dusty old XP install to a shiny new Windows 7 install. I'd copied everything across to Win7 and then was deleting any unneeded files there.
In a couple of cases, once I'd tidied directories out, I found that I couldn't delete them from within Windows Explorer. Well, I could delete them momentarily before they instantly reappeared.
It wasn't quite the same problem as the one described here — I didn't receive any error message on deletion for one thing — but the solution was the same: open a command prompt and use the rmdir command to prevent the pesky thing returning again once and for all.