Sí, la declaración es
Código Delphi
[-]sz_CERT_STORE_PROV_MEMORY = 'Memory';
Y es un PAnsiChar.
En la última modificación eliminé el control de errores por simplificar el código pero puedes añadir de nuevo la función CheckError y comprobar los punteros devueltos por las funciones del CryptoAPI
De todas formas yo probé con la constante de cadena como tú y no me falla.
¿Cómo está declarada y dónde en tu código la función CertOpenStore?