Googled it, and found lots of articles about this error. Most suggestions was about installing hotfixes, adding permissions directly in the SQL db's, changing environment variables, installing latest win updates etc etc.
But I had a feeling it had more to do with the accounts running the Search services or application pools. I had changed some of these from farm account to a specific service account, for security reasons and what MS recommends. But, after having changed back the SharePoint Search Host Controller to the farm account, (Go to "Security", "Configure service accounts" and select the "Windows Service - Search Host Controller Service", make an IISRESET afterwards) and all started working instantly.
Maybe not recommended, but I will keep it running like this. The message in the Health Analyzer has not come back so, so far so good.