Hi,
We have the same issue. We use Horizon 7.1 and deliver Server2016 desktops (non-persistent).
After a lot of trial & error with Persona management we managed to get a reasonable stable situation (but not completely).
Persona settings: roam local settings enabled, exclude AppData\Local\Packages
For the search in the start menu to work, we had to enable the Windows Firewall service (At some point one needs to stop asking why...)
Sometimes it still happens that the search menu stops working. A logoff can help, but sometimes we also have to remove the Appdata\local\TileDataLayer folder from the users profile to get it fixed.
I'm hoping to find some time into testing with VMWare User Manager profiles in stead of Persona to see if it works better then.
Regards,
Michiel.