Perhaps related: "How come someone notarized my app?"[0]
It mentions that anyone with an apple developer ID can notarize a qualifying app and submit this notary to the Apple Notary Service. However, the proof of notarization—the notarization ticket—might not be stapled to the application.
In the case of no stapled ticket, Catalina contacts the notary service to see whether a ticket exists. If so, the app is good to go.
[0]: https://eclecticlight.co/2020/05/22/how-come-someone-notariz...
EDIT. More informative link here[1]. It specifically outlines what happens on first run of an app. (and there's a great diagram if you scroll down)
[1]: https://eclecticlight.co/2020/01/27/what-could-possibly-go-w...