You are absolutely correct. I found the SHFS files in the default directory C:/Programs....
However, the environment variable is set to SHFS C:/PROGRA~1/SIDEEF~1/shfs when I check in the "about" dialogue (which is why the files were validated without an error)but Houdini is still looking in the custom directory.
I solved the problem for now by just copying the contents of the shfs folder in the default location to the custom location.
Now Houdini seems to find them on startup but the environment variable is still the default one and this kinda contradicts the point of the shfs directory.
Seems to be a bit of a mess.
Thanks for the help.
EDIT: Soory to say, it didnt fix the issue. I worked once. I ust started Houdini again and the error was back.

At least we have a hint now. I need to figure out if I can edit the env variable to fix it. This is really weird.