The script provided by Microsoft in the Knowledge Base article:
How to restore the missing Windows Installer cache files and resolve problems that occur during a SQL Server update
...found the missing files and allowed me to advance a bit:
Save the script to your desktop
Run it using CMD
cscript scriptname.vbs scriptoutput.txt
Find all the copy commands in the text file and use them to populate your Windows installer folder. Those missing files are causing your issue.
EDIT
The step 3 needs a little more explaining:
The text file produced from the VBS script contains various recommendations and mostly suggests to copy the files from certain locations (more on that later) to the %windir%\installer path where they should be in order for any upgrade/patch/repair process to work.
In my case, I had sqlserver 2008R2 SP1 so the output textfile basically told me "I need certain vanilla files and certain SP1 files"
Here is the script asking for vanilla files, which can be found in a stock sqlserver2008r2 installer DVD
Copy "C:\Source\Sources SQL 2008\SQL 2008 R2\SQL2008R2_source\x64\setup\sql_engine_core_inst_msi\sql_engine_core_inst.msi" C:\Windows\Installer\2d620c2b.msi
And here is the script asking for SP1 files :
Copy "g:\10bb0cd00ccb163360\x64\setup\sql_engine_core_inst_msi\sql_engine_core_inst.msp" C:\Windows\Installer\2d8607e0.msp
SQLSERVER will remember where it found those files the first time it had to use them, but this location might not exist anymore if, as in my case, someone did tons of cleaning on the server and deleted all of you precious files.
You will need to modify the first part of the path so it matches the location of your extracted DVD and of your extracted SP1 patch. To extract the SP1 patch, you can run the following command in a CMD prompt
c:\path\to\file\SQLServer2008R2SP1-KB2528583-x64-ENU.exe /x
Notice, the /x at the end, this command will open a small window asking where you want the content to be extracted.