GRANT and REVOKE are very complex structure commands and sometimes it becomes difficult to track all small details. It will be nice if you can post the Queries you ran to Grant the Execute permission on user, are these both user member of any ServerRole ? did you use GRANT command with GRANT option ?
from your description and other comments i see User_1 is Grantor and if it is DB_Owner that means it has all privileges. so what about User_2 ? is it member of any server role?
try this script below. it is just demonstrating GRANT and REVOKE expected behavior on SQL 2008-R2-SP1.
in this example dbo is granter and user1 is grantee.
see the output image first two line of output is showing the right User who is executing the procedure. but after Doing Revoke on User_1, we have a error message.
Also, After GRANT i can see the recird in sysprotect ut after revoke i do not see any record for user1.
IF Object_ID('Pr_TestUserPermission') IS NOT NULL
DROP PROCEDURE Pr_TestUserPermission
GO
CREATE PROC Pr_TestUserPermission
AS
BEGIN
PRINT 'This Procedure is currently executed under user ' + USER_NAME()
END
GO
GRANT EXEC ON Pr_TestUserPermission TO user1
SELECT object_name(id), user_name(uid) FROM sysprotects WHERE user_name(uid) = 'User1'
EXECUTE Pr_TestUserPermission
EXECUTE AS LOGIN='User1'
EXECUTE Pr_TestUserPermission
REVERT
REVOKE EXEC ON Pr_TestUserPermission FROM user1
SELECT object_name(id), user_name(uid) FROM sysprotects WHERE grantor = USER_ID('user1')
EXECUTE AS LOGIN='User1'
EXECUTE Pr_TestUserPermission
REVERT


EDIT:1
I found interesting reason for this. it's the syntax of REVOKE statement.
check the below example. in this example user1 is db owner and Granter while user2 is grantee.
check the output. image below.
using the common syntax "REVOKE EXEC ON SP FROM USER2" that updates the sysprotect but does not actually revoke the permission. but if we use the another syntex "REVOKE EXEC ON OBJECT::SP From user2" then it does the actual revoke of permission and we can see that in the result attached below.
SET NOCOUNT ON
IF Object_ID('Pr_TestUserPermission2') IS NOT NULL
DROP PROCEDURE Pr_TestUserPermission2
GO
CREATE PROC Pr_TestUserPermission2
AS
BEGIN
PRINT 'This Procedure is currently executed under user ' + USER_NAME()
END
GO
GRANT EXEC ON Pr_TestUserPermission2 TO user2
SELECT object_name(id), user_name(uid) FROM sysprotects WHERE user_name(uid) = 'User2'
EXECUTE Pr_TestUserPermission2
EXECUTE AS USER='user2'
EXECUTE Pr_TestUserPermission2
REVERT
REVOKE EXECUTE ON Pr_TestUserPermission FROM user2
SELECT object_name(id), user_name(uid) FROM sysprotects WHERE grantor = USER_ID('user2')
EXECUTE AS USER='user2'
EXECUTE Pr_TestUserPermission2
REVERT
REVOKE EXECUTE ON OBJECT::dbo.Pr_TestUserPermission2 FROM user2
SELECT object_name(id), user_name(uid) FROM sysprotects WHERE grantor = USER_ID('user2')
EXECUTE AS USER='user2'
EXECUTE Pr_TestUserPermission2
REVERT
