The libraries and the executable are packaged and sent to the notarization service, and the response is that the notarization is successful. What do you mean "libraries and the executable"? The libraries should be bundled inside the executable. If not there, they should be bundled inside an installer package, or perhaps something even more esoteric.
Checking with codesign, all looks to be good: Really? What about "test-requirement: code failed to satisfy specified code requirement(s)"?
I strongly recommend against using that "notarized" requirement or the "--check-notarization" flag. I had to double check these because I didn't recognize them. I did find one of those flags in the codesign man page and I saw Eskimo reference the other one. So, they are valid, but that doesn't mean they do what people think they do.
There is only one way to check notarization. You have to download the notarized file and run it. If it works, then the notarization is successful. There is absolutely no other tool, command-line trick, or codesign operation that will suffice - absolutely nothing. You must download the app with Safari, run it, and it must work.
There are quite a few validation stages that a notarized app must pass. I don't know anything about your software, so I can't begin to speculate about where the problem lies with that particular build. Generally speaking, if you correctly build an app in Xcode, archive the app, and the submit the app to the notarization service, then it works perfectly 99.999% of the time. I can't say 100% because I'm sure there is always some oddball case or the notarization service is down.
When people have problems with notarization, here are the top explanations:
1) the notarization service is down
2) the Xcode project is not correctly structured and is hacked up
3) the developer isn't building the project with Xcode and did something wrong
4) the developer isn't building the project with Xcode, is using some crazy 3rd party development tool, and has no idea what can of worms they have opened up upon themselves
My guess is that you are in category 3, or maybe 4. People who report notarization problems are almost always category 4.