Found the issue.
It seems that when you work with writable volumes, the second time you login the Windows Shell Experience Host doesn't register correctly.
This causes not only the start menu but the whole taskbar to malfunction.
You can fix this by running the following powershell command:
Add-AppxPackage -DisableDevelopmentMode -Register "C:\Windows\SystemApps\ShellExperienceHost_cw5n1h2txyewy\AppxManifest.xml"
I chose to add this command in the shellstart.bat of the writable volume but keep in mind that this adds a couple of seconds to each login so there might be a better way to do it.
UPDATE: Seems I hit a snag as this only works on domain admin accounts.
Strange since I thought this would be executed in the context of writable volumes and not the user.