@Jccr,

Does your guest Wi-Fi have the same SSID as the regular Wi-Fi, if this is the case, the devices may be connecting to that network and being blocked from seeing other devices on the network.

Do the devices recover after a short while?

I would recommend trying to set up the devices while the guest network is enabled, the network settings on the devices can be reset using a soft reset, which will keep the device name, location, and automation. 

Setting an IP reservation in your rotuer may help to create a stable connection to the router.

Lastly, is there a large distance between the devices and the router, like would the guest network potentially cause enough interference that would prevent it.