What could cause SQL Server to deny execution of a SP at first, but allow it later with no privileges change?

A user just complained he was denied the execution of a procedure. I went to check and verified he had the privileges to execute it. I didn’t change anything (and right now I’m the only one with admin privileges do to so if needed) and after two unsuccessful attempts he tried to run the SP for the third time and it worked.

I have XE configured to catch error messages and it captured twice the error code 229:

The EXECUTE permission was denied on the object ‘storedProcedureName’, database ‘databaseName’, schema ‘schemaName’.

Is there any situation where this behavior is expected?

Microsoft SQL Server 2014 (SP3-CU-GDR) (KB4535288) – 12.0.6372.1 (X64)