TLDR
If removing the Microsoft Store Notepad did not help, you can run reg delete "HKLM\Software\Microsoft\Windows NT\CurrentVersion\Image File Execution Options\notepad.exe" /f as admin to clean up the redirection record completely and then re-install notepad2 that will re-create the record in the desired form.
Details
This problem annoyed me enough, so I decided to dig a bit deeper, user Chino Chang does have a point in their answer.
There is pretty good description of how Image File Execution Options works in the linked article. The salient point is that there is now a UseFilter value under the Image File Execution Options/filename key, and if it is set, then not every notepad.exe will be redirected to yours, but just those that are specified in the subkeys. Since the Microsoft Store one does not seem to be specified it does not get redirected.
Version 6.1 extends the scheme to differentiate according to the whole name that is supplied for the executable. The extension is a little complicated because, of course, the whole pathname can’t itself be a subkey. If the subkey just for the filename contains a particular value (to show that the extension applies) and a suitable subkey (containing a particular value whose string data matches the executable’s whole name), then the function returns the deeper subkey instead.
Extension to a subkey for the whole name of the executable applies only if the subkey for the filename contains a REG_DWORD value named UseFilter whose dword of data is non-zero
If the UseFilter value is absent from the subkey for an executable’s filename, or if it is present but has the wrong type or size or is zero, then all executables with this filename have the same Image File Execution Options and the subkey for the filename is what the function sticks with.
Given that the subkey for just the filename has a correctly configured UseFilter, it may have any number of subkeys that are each for a different pathname. The names of the subkeys are immaterial. What matters is whether a subkey has a REG_SZ value named FilterFullPath whose data matches the executable’s whole name
This was my case, I did have UseFilter and I did have the subkeys with some paths. Getting rid of these resolved the issue.
Note: Notepad store app can be deleted with the following command if required:
Get-AppxPackage | Select-Object -ExpandProperty PackageFullName | Select-String notepad | Remove-AppxPackage