My Lenovo came with a recovery partition from which I could reinstall Windows. However, I suppose it would also automatically reinstall crapware, which is beside the point.

The solution was to download an official Windows 8 copy from Microsoft's website - the Windows installer will get the license key from the EFI.

Not as good as a recovery disk, as you will need to download and install manually all drivers, but vetting everything is part of the point.

EDIT: for those looking, this is the link from where I downloaded the Windows 8 binary from Microsoft website: http://windows.microsoft.com/en-us/windows-8/create-reset-re...