xcrun notarytool fails with missing keychain item

Question

I am using xcrun notarytool store-credentials to set my credentials for the notarization process of my executable. I use the command below to store the credentials:

%xcrun notarytool store-credentials --apple-id $APPLE_ID_USER \
                                    --team-id XYZ --password \
                                    $APP_SPECIFIC_PASSWORD xyz.io --verbose
Credentials saved to keychain.

Running xcrun notarytool submit succeeds for just a few minutes and rerunning the same command on the same executable all of the sudden returns this:

xcrun notarytool submit ...
Conducting pre-submission checks for xyz.dmg and initiating connection to the Apple notary service...
Error: No Keychain password item found for profile: xyz.io

Run 'notarytool store-credentials' to create another credential profile.
Error: Process completed with exit code 69.

I can still see the item in the keychain. Any idea what this might be caused by? I have a second Mac where the problem doesn't happen.