Permissions using .NET SqlDependency
After days of debugging, one little setting made all the difference.

If you get this error mentioned in OP, please check the owner of the DB-role used! It wasn't set to dbo in my case. Changing that made it work - see comments for history!