I debugged the problem a little using strace.

As describe in this post it's mostly about the Trash folder, with "Use recycle bin" enabled or working with files you don't have write permissions to. In the first case trouble arises, when using external media, like USB drives or other mounted partitions for example.
With "Use recycle bin" enabled: Deleting files in /tmp/ works fine, because the trash folder in my home directory is used. But deleting files from a drive mounted to i.e. /mnt/ fails.
That happens when XnView tries to create a trash folder in the root folder of the partiton or media you are working on and is not able to do so. There might be several reasons for that:
1. Trash folder doesn't exist and user running XnView has no permissions to create it in the root directory of your partition/external media.
2. Trash folder exists and user running XnView has no permissions to write or read.
Workarounds: (pick one)
1. Undesirable workaround (because recycle bin will obviously be inactive after that): F12 > General > File operations > disable "Use recycle bin"
2. Depending on your permissions, this might be unsafe: Change mount options to allow your current user to write in the root folder of the media (/etc/fstab: add uid=<your current user id>, remount)
3. Create a Trash folder in the root of your mounted media/partition (mkdir .Trash-1000) and change owner to your user (recursively)
3.1 Attention. Running XnView with a non-root user and the trash folder is owned by root.root with permissions 777 doesn't seem to work!
4. In case the trash folder is working fine and you just don't have permissions to delete the files: Adjust file permissions of your pictures (again remember security implications on a multi user system if you chmod 666)
@Pierre: For a permanent fix I'd suggest to include an error message, if XnView is not able to create or write to the Trash folder while "Use recycle bin" is enabled, offering an option to remove the file directly instead of just pretending to do so. This saves a lot of time for any user deleting lots of files.