So to confirm, on a fresh Wordpress install with that setup /non-existing-url definitely returns 404, so it's not specifically the custom permalink that's the cause.
It may be worth posting your .htaccess in case it's been modified.
However I'd suspect that one of the plugins you have is helpfully adding this feature, and I'd suggest temporarily disabling Redirection and SEOPress to see if it's them. Once you figure out which one it is you can see if there's a way to disable this specific behaviour in that plugin
If you want to, it would be easy to manually add an .htaccess rule to make /anything 404, but that puts a fix on top of a problem and will quite possibly break other things, so I agree with the point of your post which would be figure out what's doing it if possible.
EDIT: Query Monitor shows you which URL rules the current page matched against, however I don't know if it'll be useful here where there's a redirect. Worth knowing about if you don't already as it's a great tool for debugging URL rewrite issues.