Do they have to be from the App Store, or "just" notarized?

Notarized works just fine.