I’m testing the availability topic with a Sonoff basic running Tamosta. When the Sonoff is rebooted, the item becomes unavailable in Home Assistant and availability never returns. Is this the expected behavior? It would make sense to me that the item become available again once the reboot is complete, but I’m not seeing that happening.
There needs to be something in the tasmota start up that sends a message with the availability_topic: and a payload of payload_available:.
I don’t have a sonoff, but I suggest you look for something in the configuration that allows you to send something at boot - and make sure it matches exactly, case matters 
I can see in the Tasmota console where it’s sending the online message. The payload matches exactly, which the exception that the string “retain” is appended.