In order to clean up my project structure, I moved a folder into another (new) folder through the TFS Power Tools Shell-Extension (Rename/Move).
After checking the history at the new place, the move is the only entry. (I tried one folder up, down, even on single files in the moved folder.. same result.)
I had also put on some labels on versions of the folder before the move, since there were some important states of the code I wanted to get back to.
So.. what went wrong, and how can I either get the history or at least find out the label names again and check out those versions?
Turns out it is pretty easy.
In Visual Studio 2010, go to Tools->Options. There you can find the option to show "deleted" items (roughly in the middle of the dialog box). The old folder got deleted during the move - it will be displayed again after activating that option. (They will be kind of grayed with a red cross.)
Labels seem to have disappeared, though, so I had to go by version.
In the Source Explorer you have the normal operations again - like View History or Get.