The problem was that I did not add a reference to "Microsoft.Interop.Excel" to the project, but I am confused why I had to do that at all. I already said
"Imports Excel = Microsoft.Office.Interop.Excel"
and the IDE did not complain about it.
Also, I was unable to find this lib in the COM / Assembly search window.
I had to browse for it, and I found it under
C:\Windows\assembly\GAC\Microsoft.Office.Interop.Excel\12.0.0.0__71e9bce111e9429c\Microsoft.Office.Interop.Excel.dll