Thanks for your comments Atanas,
I was able to solve the issue in the meantime. For those who run into the same problem like me, here is another thing they can be looking out for:
What I did before:
1. I used the Azure SQL Migration Wizard to copy the DB from development to production. It works quite well and copies all objects and the data without much ado.
2. I published the SF project using the VS publishing mechanism. The connection string would be replaced automatically.
For some reason, the SQL Migration Wizard did not only copy the dbo objects, but also created the same objects AGAIN in the schema of the owner of the target db. So if I had a user "test" with a schema "test" in the target db and an object "dbo.table" from the source db, then it would create both a table "dbo.table" and "test.table" in the target db. So I ended up with a duplicate of each object in the target db. One copy in the dbo schema and one copy in the "test" schema. Only the dbo schema tables however would be filled with data. The objects in schema "test" remained empty.
What happened when SF connected to the DB and started to look for the data was that it came back and reported above error (rightfully so). It would go look for "test.sf_page_nodes" instead of "dbo.sf_page_nodes". It would find the table, too, because it was created by the SQL Migration Wizard. But it would be empty. Hence the error message.
How to fix it:
Make sure that the default schema of the db_user is set to dbo. See attached image. At least that's how I did it. It will then use the right tables. If you drop the DB and run the SQL Migration Wizard again it will also avoid that objects are created twice (see above).
Not sure if there is an option in the SQL Migration Wizard to do this from the outset. If someone has the time to investigate this then that would be great.
I hope this helps others who may run into the same issue.