Preventing Bob from sales from selecting other people's messages

Suppose that Bob can retrieve all messages, as follows, and we are not happy with it:

EXEC Exchange.ShowAllMessages;

Suppose that we don't want him to read anything related to messages, so our knee-jerk reaction is this:

REVOKE EXECUTE ON Exchange.ShowAllMessages FROM Bob ;

This does not work - Bob still can execute Exchange.ShowAllMessages, just as he could before. The reason is simple: everyone were granted the privilege to execute that procedure:

GRANT EXECUTE ON Exchange.ShowAllMessages TO PUBLIC ;

This privilege still exists after we have run our REVOKE command, and Bob still belongs to PUBLIC. The following brute force method prevents Bob from reading messages, but at a steep price: no one else can read all messages any more:

REVOKE EXECUTE ON Exchange.ShowAllMessages FROM PUBLIC ;

The following script does a better job: Bob cannot invoke Exchange.ShowAllMessages directly any more, and all others can execute the procedure exactly as before:

GRANT EXECUTE ON Exchange.ShowAllMessages TO PUBLIC ;
DENY EXECUTE ON Exchange.ShowAllMessages TO Bob ;


Note, however, the emphasis on the word directly: in some cases Bob still can execute the procedure indirectly, if it is called by another procedure he has access to.Suppose, for example. that we have two schemas, Exchange and Sales, both created with the same authorization:

CREATE SCHEMA Sales AUTHORIZATION dbo;
GO
CREATE SCHEMA Exchange AUTHORIZATION dbo;

Unfortunately, Bob can run the following procedure, and he will still see all the messages:

 CREATE PROCEDURE Sales.ShowMySalesWithBackDoor
AS
    BEGIN ;
-- do something here
        IF SUSER_NAME() = 'Bob'
            BEGIN ;
                EXEC Exchange.ShowAllMessages ;
            END ;
    END ;

So, we have spent some time trying out different approaches, and nothing works so far. Clearly we are out of our depth - otherwise we should have completed this seemingly trivial task long ago.

It is time to do some learning - should we have deep understanding of SQL Server security, we would have solved this problem easily. To improve our knowledge, I would suggest the following two resources:
Expert SQL Server 2005 Development by Adam Machanic,and Protecting SQL Server Data by John Magnabosco.