SQL Server Permission Check Timing

Ok, on the basis of the above comment and as per my suspicion - it seems as though you are trying to execute dynamic SQL within your stored procedure.

What you need to remember is that when you do this it does not get executed within the context of the stored procedure - it gets executed within a new session. Because of this, the fact that the statement is being called within a stored procedure is a moot point, and you will need to grant explicit permission on the objects that your dynamic SQL is using.

If you don't want to do this I would refactor your stored procedure to not use dynamic SQL.

The below link from Microsoft should help you with your problem:

PRB: Security Context of Dynamic SQL Statements Inside a Stored Procedure (Wayback Machine archive)

This behavior occurs because a dynamic execution query (sp_executesql or EXECUTE) executes in a separate context from the main stored procedure; it executes in the security context of the user that executes the stored procedure and not in the security context of the owner of the stored procedure.

This is also discussed in the (more current) Microsoft Docs article:

Writing Secure Dynamic SQL in SQL Server

Executing dynamically created SQL statements in your procedural code breaks the ownership chain, causing SQL Server to check the permissions of the caller against the objects being accessed by the dynamic SQL.

The EXECUTE AS clause of CREATE PROCEDURE can only be used to impersonate a user (not a login) and the scope of impersonation is restricted to the current database. The sysadmin permission is associated with the login, not the user, so you receive a permissions error.

The correct way to grant CREATE DATABASE here is to sign the procedure. The process is a little involved because we want to sign the procedure to grant a server-level permission, but each step of the process is reasonably simple:

First, create a certificate and login in master with the CREATE ANY DATABASE permission. The certificate will later be copied to the target database to allow procedure signing.

USE master;
GO
CREATE CERTIFICATE CreateDatabaseCert
   ENCRYPTION BY PASSWORD = 'password'
   WITH SUBJECT = 'Create Database',
   START_DATE = '20140101',
   EXPIRY_DATE = '20141231';
GO
CREATE LOGIN CreateDatabaseLogin 
FROM CERTIFICATE CreateDatabaseCert;
GO
DENY CONNECT SQL TO CreateDatabaseLogin;
GO
GRANT CREATE ANY DATABASE 
TO CreateDatabaseLogin;

We now need to copy the certificate to the database where the procedure will be run. There are a couple of ways to do this, but the most compatible is to read and write the certificate via a file. This next step writes the certificate:

BACKUP CERTIFICATE CreateDatabaseCert 
TO FILE = 'C:\Temp\CreateDatabase.cer'
WITH PRIVATE KEY 
(
    FILE = 'C:\Temp\CreateDatabase.pvk',
    ENCRYPTION BY PASSWORD = 'password',
    DECRYPTION BY PASSWORD = 'password'
);

Now we switch to the target database, restore the certificate, and delete the temporary files:

USE Sandpit;
GO
CREATE CERTIFICATE CreateDatabaseCert
FROM FILE = 'C:\Temp\CreateDatabase.cer'
WITH PRIVATE KEY
(
    FILE = 'C:\Temp\CreateDatabase.pvk',
    ENCRYPTION BY PASSWORD = 'password',
    DECRYPTION BY PASSWORD = 'password'
);
GO
--EXECUTE sys.sp_configure 'show advanced options', 1;
--RECONFIGURE;
--EXECUTE sys.sp_configure 'xp_cmdshell', 1;
--RECONFIGURE;
EXECUTE sys.xp_cmdshell 'ERASE C:\Temp\CreateDatabase.*';

Now create the procedure, and sign it using the certificate:

CREATE PROCEDURE dbo.CreateDatabase
(
    @DatabaseName SYSNAME
)
WITH EXECUTE AS CALLER
AS
BEGIN

    SET NOCOUNT ON;
    DECLARE @cmd NVARCHAR(max);
    IF COALESCE(@DatabaseName,'') <> ''
    BEGIN
        SET @cmd = 'CREATE DATABASE ' + QUOTENAME(@DatabaseName) + ';' 
        EXEC sys.sp_executesql @cmd;
    END
    ELSE
    BEGIN
        SET @cmd = 'INVALID DATABASE NAME';
        RAISERROR (@cmd, 0, 1);
    END
END;
GO
ADD SIGNATURE TO dbo.CreateDatabase
BY CERTIFICATE CreateDatabaseCert
WITH PASSWORD = 'password';

To test this works, we create a new login and user with permissions to execute the procedure only:

CREATE LOGIN test WITH PASSWORD = 'password';
CREATE USER test FROM LOGIN test;
GRANT EXECUTE ON dbo.CreateDatabase TO test;

The test itself:

EXECUTE AS LOGIN = 'test';
EXECUTE dbo.CreateDatabase @DatabaseName = 'NewDB';
REVERT;

The database is created successfully. To clean up, run the following:

DROP DATABASE NewDB;
DROP USER test;
DROP LOGIN test;
DROP PROCEDURE dbo.CreateDatabase;
DROP CERTIFICATE CreateDatabaseCert;
GO
USE master;
DROP LOGIN CreateDatabaseLogin;
DROP CERTIFICATE CreateDatabaseCert;

For more information on permissions, see Erland Sommarskog's excellent article.