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

Perhaps the user had an invalid Kerberos ticket (for example expired), which caused the two "access denied" errors. At some point in time after that the user's workstation contacted a DC and renewed the ticket, allowing the user to execute the procedure the third time.

Another possible root cause would be a misunderstanding of how a stored procedure definition is terminated. Take this for example:

CREATE OR ALTER PROCEDURE dbo.MyTestProc
AS
BEGIN
    SELECT result = 1;
END
GRANT EXECUTE ON dbo.MyTestProc TO [SomeUser];

The intention here is to define the procedure and then grant permissions to it.

However, the first time that batch is executed, permissions on dbo.MyTestProc will not change. The first time the stored proc itself is executed, via EXEC dbo.MyTestProc, the permissions will be granted to allow [SomeUser] to execute the proc.

The corrected batch to create that proc and grant permissions to it would be:

CREATE OR ALTER PROCEDURE dbo.MyTestProc
AS
BEGIN
    SELECT result = 1;
END
GO
GRANT EXECUTE ON dbo.MyTestProc TO [SomeUser];

The GO between the procedure definition, and the GRANT statement means that when you execute that batch, the procedure will be created and the grant will immediately take effect.

If the proc was defined incorrectly, as shown above, the user may not have been able to execute it. If you then executed the proc as a sysadmin, the first execution of it would have granted them access.

Related to Josh's answer: An alternative could be that this person was a member of an AD group for which there was an explicit DENY to do the operation. And then this person was removed from the AD group with that DENY.

I'm talking about a user in the database. A user that points to a login, where that login points to an AD group i.e. the deny could have been done to as user, in the end pointing to that AD group. Your person might have been member of that AD group. Pretty much the same as Josh's example, but in reverse.

Not as likely as Josh's example, but plausible.

If the Windows user account was added to an Active Directory (AD) group in the meantime, and that AD group had permission to run the procedure, then that could create this scenario where a user gained access to a procedure with no changes within SQL Server.

Also get the network admin to check if the user logged off and on again. Group membership only gets assigned at logon so if the user was added to a group and had not logged off he would not have had that group membership in his token. - Spörri

Related Q&A: How do I assign an entire Active Directory group security access in SQL Server 2008?