Same issue. Has anyone found a solution to this since the last post 1 year ago? This must be happening to everyone using Tasmota no?
Not all all, all my Tasmota devices are available at HA restart. Even the old ones at version 6.6
HA restart or core restart? Full system update. For me this only happens after a core restart.
Then the problem is probably in the Mosquitto add-on, not Tasmota.
I found out that reloading the Tasmota integration after EACH reboot, brings the devices back online. This worked every time.
Integration - TASMOTA - 3 dots - reload
No Tasmota Option19, no MQTT reconfig, just reload the integration
IMHO, the startup order is causing issues. I have however no idea on how to change it
Thank you, it seems this bug is still there and not fixed as you said.
Reloading the integration doesn’t work for me, I had to add the MQTT publish automation which is a pain to maintain of course…
Wow, two years and this issue is still a thing 
Sadly i am not using tasmota anymore and switched to esphome (shortly after my posts above) and they are rock solid since ~2 years.
pOpY
Completely forgot about esphome, it’s been ages that I use Tasmota.
Not sure now if I should thank you or hate you 
It looks so tempting to try the switch but I have so much stuff to change or adapt that it scares me!
All my plugs seems to be fully supported, of course, it’s a provocation.
I know what you mean 
Yeah, you have to fiddle arround with your yaml’s to reproduce your current tasmota devices.
But when you are into it, it’s such a good solution to work with.
In my case i have setup my yamls with a “split” config, so a device_base.yaml, and other sensors, … in the device yaml which includes the device_base.yaml.
This way you dont have so much copy paste code and when you want to change something, have to change it 100 times 
Sure it’s a provocation 
Have fun
I definitely have to plan migration to Esphome
Found 2 of the Tasmotas not available today, even without an HA restart in between.
My automation didn’t work; found out my Tasmotas does not subscribe to the topics to process commands sent via MQTT publish (no Subscribe messages at reboot).
I did only test the command on the console, my bad.
Anyway on the information tab I found out they subscribe to a couple of group topics including the tasmotas one:
This is very convenient for the automation as you only need to publish one command to reboot them all and forget about its maintenance:
On further inspection via MQTT explorer I found out the root cause of the issue, meaning why the Tasmota integration doesn’t work properly.
The integration itself doesn’t have any issue, it’s the Tasmota firmware failing to update properly the LWT (Last Will and Testament) topic.
Both the unavailable Tasmotas were Offline instead of Online.
Seems the integration is relying on the LWT to detect the current status of the Tasmotas.
The LWT should be updated with the correct status once it changes but clearly it doesn’t work as expected.
The status could be set Offline for a multitude of reasons seems, from Wi-Fi failures to MQTT disconnections, etc.
Somewhere in the code it’s not set back to Online when it should (I’m using v14.6.0 and upgrading to v15 now).
Rebooting the Tasmotas clears the LWT (which is retained so it sticks unless updated) with the correct status.