All of our users who have the user type 'Information Worker' have the permission to delete records, all except one user who was recently added. Her permissions are fine, the access controls on the record, folder, classification, etc. all allow her to delete but the option is greyed out for her. All other info workers can delete with no problem.
Usually the menu item is not grayed out from the right-click menu, it just won't appear. Are you refering to maybe a custom toolbar? Can they check if the "Administrative Tools->Delete" menu appears when right-clicking on the record?
you're right, the option to delete won't appear on their right-click menu and they don't have the 'administrative tools option' only file - delete on the Standard toolbar. I checked with another Info worker and they have the 'delete' option. weird!
I bet the user's profile for some reason isn't at information worker. Typically information worker doesn't have that right, but sounds like you've handled that. Have you triple checked that the user is not "using profile of" a location with a different category?