Found a fix, a real one. I tested this with four users a few weeks ago and have not heard from them since then.
Summary: Purge the Photos app from the system (for everyone) and reinstall from the Store or from the appx/msix installer
The following commands need to be run in an elevated PowerShell
Step 1: Get the name of the provisioned package
Get-ProvisionedAppxPackage -Online | where {$_.DisplayName -like "*Photos*"}
Step 2: Remove the provisioned package
Remove-ProvisionedAppxPackage -Online -PackageName [PackageName_from_step1]
Step 3: Verify if the app is still installed for anyone
Get-AppxPackage -AllUsers | where {$_.Name -like "*Photos*"}
Step 4: Remove the app for everyone
Remove-AppxPackage -AllUsers -Package [PackageFullName_from_step3]
At this point, the Photos app should be purged. Rerun step 1 and 3 commands to be sure.
Step 5: Reinstall the app
Option 1: Install from the Store. This will install the app only for the current user, it won't be provisioned for new users. This is probably fine for personal computers.
Option 2: Download the appx/msix installer (search "download appx" if you don't know how to do this). Then, run this command:
Add-AppxProvisionedPackage -Online -SkipLicense -PackagePath [path_of_downloaded_file]
This should reinstall the app for everyone as well as new users.
Followed the steps provided. Unfortunately, this did not resolve the issue for me.