To my astonishment, I found out that the WSP was only deployed to all the Frontend servers in my Farm but not to the Index Server :(
Cause
A wsp contains a manifest.xml, which looks like this:
When you build a WSP using WSPBuilder, by default the Solution element does not contain a DeploymentServerType attribute, which is the cause of the problem. The DeploymentServerType has the following description:
DeploymentServerType : Optional. Default=WebFrontEnd. This attribute indicates the target of your solution to either a web front end server (WebFrontEnd) or an application server (ApplicationServer).
Solution
Make sure the DeploymentServerType is specified in the manifest.xml. To accomplish this, you need to edit the WSPBuilder.exe.config (in my case in the folder C:\Program Files\WSPTools\WSPBuilderExtensions), and add the attribute DeploymentServerType.