I checked my stunnel.con file and I find I'm not using dns names, only IP addresses. That's probably the reason it works on my side. If you are using dns names, most likely we need to add the dnscache service as a prerequisite.
You may want to open an elevated command prompt and try:
sc config stunnel depend= dnscache
Then reboot to see what happens
From: John Smith <java.dev.mtl@gmail.com>
Date: Mon, 22 Sep 2014 11:40:43 -0400
To: Jose Diaz<josealf@rocketmail.com>
Cc: <stunnel-users@stunnel.org>
Subject: Re: [stunnel-users] Stunnel as windows service doesn't start on restart.
Elasticsearch. But it's stunnel itself that won't start. The stunnel service shows as started, but no logs are produced. Once I stop stunnel service and start it again the logs shows up. Also stunnel with Automatic Delayed start works fine.