I just figured it out. I'm using the german translation of Calibre, the hotkey is given as "Löschen" (german for delete) in the menu. When I switched to using the english translation, the delete key works as advertised. When I switched back to the german translation, again, the delete key didn't work.
I believe that has some significance to our problem.