Cannot activate Windows 7 on a stickerless Lenovo

I have a Lenovo T520 laptop that came with Windows 7 Professional.

The laptop does not have a Windows license sticker, but it came with legal system preinstalled. I was able to retrieve the Product Key with NirSoft ProduKey.

I am sure that the key is correct, because I have used it before doing system recovery.

This time I wanted to make a clean reinstall though. After reinstalling, the Product Key is not accepted by Windows. The error message that I receive says:

A problem occured when Windows tried to activate. Error Code 0xC004E003

What should I do to activate Windows with this product key?

It turned out that there actually was a sticker with the license key. The sticker was located behind the battery.