Yeah Dilbert, I have seen this kind of weirdness before. Usually I see it with network drives though. I wonder if the folder creation process occurs separately from the Explorer process? And then the usual notification of changes doesn't occur occasionally?
Can't find anything useful in the MS Knowledgebase, but then it's hard to think of particularly useful search terms in this context!
Just out of curiosity - did you try hitting F5 when your new folders failed to appear? If not, try it next time this happens.
(And of course remember what I said about having a poltergeist in your machine...)