I needed to initialize a key container, like so:
Private Const CRYPT_NEWKEYSET = 8
Call CryptAcquireContext(lngContext, vbNullString, MS_STRONG_PROV, _
PROV_RSA_FULL, CRYPT_NEWKEYSET )
Then the other call (using CRYPT_VERIFYCONTEXT) works.
The full (fixed) module:
Option Compare Database...