I found that when one of our machines reboot, I see audit errors in the event viewer saying that SQL Server Express cannot logon with NT Authority\System, there after my service application gives a similiar login error and does not start.
If I then start my service application manually (with services.msc), it starts perfectly. So the problem is only with rebooting.
So it looks like it is an issue with when the System account is available when SQL server service starts?
I have now switched to mix mode authentication and created an sql server account. I have changed my connection string to use it and on reboot I still get SQL Server express complaining about not being able to login with this account and also my service application gives the same error. Once again, manually starting my service application works.