You've not got that bit quite right. The user has to have EXECUTE permission on the SProc, but the SProc runs with permissions on the table of the person that CREATED the Sproc (you can also impersonate a user/role/whatever if you want to, but that is more hassle IMHO).
Our users have no permissions (none whatsoever) on any tables, view, or anything else like that, only Execute on Sprocs - so if they want to delete every Customer record they will have to do them one-by-one using the Customer Delete SProc - good luck to them! You could grant them SELECT on VIEWs, in additional to EXECUTE on Sprocs, if they need to be able to do adhoc reports - our users have "criteria forms" - lots of fields that they can set values in for the "criteria" for their report, and they can pick the columns they want in the output from a list, but they are heavily constrained - I'm sure in other circumstances more freedom would be needed. The values / choices the user puts into the criteria form is then passed to an SProc which either uses a hard coded query (with the User's parameters) or builds some SQL dynamically and runs that (again, as a specific user [with permissions] not as using the user's own permissions)
Not recommending the way we do adhoc query / reporting per se, as I say it is probably not flexible enough for some places, but the SProcs for Insert/Update/Delete should be bullet-proof on permissions.
Not sure what the consequences are, but you might also be able to use sp_ExecuteSQL. That lets you provide some SQL and a list of parameters. It is very efficient (the query plan for the SQL is cached, like a Stored Procedure is), but you do have to use identical SQL each time. So instead of
SET Col1 = 'foo',
Col2 = 'bar'
you have to do
SET Col1 = @Param1,
Col2 = @Param2
and then pass @Param1 and @Param2 to sp_ExecuteSQL. Thus the actual SQL is identical each time. I only mention this in case it fits in with how you currently generate your pass-through SQL in Access in case it lends itself to working that way.
I don't know how you set the permissions when you run sp_ExecuteSQL though ... I expect there is a way. We have SProcs that run dynamic SQL using sp_ExecuteSQL and they have a permissions certificate and all sorts of jazz for permissions, which I expect would be a PITA to set up for someone not building Big Apps ... perhaps there is a more Lightweight way to EXECUTE AS or somesuch.