There is a big difference between you running an sp from Management Studio and the users running it from Access. When you test from Management Studio you are doing so with all your admin rights. When a user executes the sp, it is the rights assigned to that specific user login.
While I am not used to using ADPs (I stick to developing in MDB/MDE dbs, normally using ODBC) I don't imagine the rules change when it comes to communicating with SQL Server and getting through its security.
When it comes to deletes, users require different permissions (when compared to select or update) so I would test by giving the users the Sysadmin server role. If your delete works then you have narrowed the solution to security and permissions by eliminating any question about anything further upstream ie the syntax of the exec being sent from VBA.
If you still can't resolve the issue from there, provide us with some details on how you have you secuirty set up, particularly whether or not you are using SQL Server or Windows Authentication.
My normal method is to use Authentication via an AD group to which I assign my users. I then create a SQL Server login for the group. The application and environment will determine how I assign permissions from there. I think you will find that this is a widely adopted method. Often I will develop a permissions script setting permissions for the varous objects.
PS - Another thought - check the permissions section of the DELETE(Transact-SQL) explanation in BOL.
PPS - Running from VBA, you are going to be creating an SQL string which you are then executing? There is something about this in the back of my mind somewhere. I'll try to get on to Google today - it may trigger something.