The Remove-AppxPackage
only removes store applications for the logged in user, even if you pipe it from Get-AppxPackage -AllUsers
I've had trouble updating apps in the past because another user had logged in and the app had been updated in their profile, it's also a known issue when using sysprep.a known issue when using sysprep.
You can identify if that is the case using this script:
Get-AppxPackage -AllUsers | Format-List -Property PackageFullName,PackageUserInformation.
In the output of this last cmdlet, check the users for whom the package is showing up as Installed. Delete these user accounts from the reference computer, or log on to the computer by using these user accounts & remove the Appx package, as you have been:
Remove-AppxPackage -Package Microsoft.BingWeather_4.7.118.0_x86__8wekyb3d8bbwe
If that still doesn't work, you could try removing the provisioning and installing it again from the Store.
Remove-AppxProvisionedPackage -Online -PackageName Microsoft.BingWeather_4.7.118.0_x86__8wekyb3d8bbwe