OK. But, in this case, I know the users have no other permissions granted, only what they've got through role membership.
I'm not trying to be a complete pain here, but are you sure they don't have any object-level permissions granted to them? I know you said you have a militant security policy, but have you run something similar to the following?
select users.name username, so.name, perms.permission_name
from sys.database_permissions perms
inner join sys.objects so on so.object_id = perms.major_id
inner join sys.database_principals users on users.principal_id = perms.grantee_principal_id
where users.name = 'suspect_username'
order by users.name, so.name, perms.permission_name;