I had this problem and my solution is to re-force publish the MQTT birth message after which Z2M re-populate device statuses -
Adjust the delay as necessary depending on the time it takes your system to properly load 
EDIT - just re-read your comments and you tried this 
automation:
# Force Publish HA Birth Message
- id: zigbee_publish_birth_message
alias: Zigbee Publish MQTT Birth Message
trigger:
platform: homeassistant
event: start
action:
- delay: '10'
- service: mqtt.publish
data:
topic: 'hass/status'
payload: 'online'