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?
DISCLAIMER: For reference of everyone that gets here, this answer is not fixing @Andreas problem, just giving some context on why this happens and offering a couple of workarounds.
Seems that losing history when moving folders in TFS 2010 is not a bug, is a "feature". (still happening in TFS2012. From this MSDN link you can read official Microsoft answer:
It is true that the folder history is lost, but the individual file history is actually not lost. It is hidden under the little "expand me" arrow at the far left on a file history line. Expand it on the oldest history entry for a file, or anywhere you see it, and you will see history of that individual file also from an old location that no longer exists.
At the top of History window you can edit Source location, put the old name and get the full history before it has been moved.
Also, is good to mention that you can get the full history back by moving/rename the branch back to the old location/name.
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.