I found a workaround that solved the problem for my case:
The needed lib is located at: C:\Program Files (x86)\Microsoft SDKs\Windows\v7.1A\Lib (at least in my case)
I copied it to: C:\Program Files (x86)\Microsoft Visual Studio 12.0\VC\lib and afterwards I could create a C++ Project without any further errors.
I could imagine that either my Visual Studio directory is lacking some libs, although I used the “Repair” functionality several times so it should be complete, or the compiler is just searching the lib in the wrong directory and somehow expects it in VS instead of at the Windows SDK folder.