I recently had this issue where I created a database user and gave delete and update permission. Yet, I was getting permission denied on a delete query.
create user username password 'whatever';
grant update, delete on table to username;
Query which gave permission denied:
delete from table where condition1 and condition2 and condition3