Hmm, apparently, I can highlight the menu item and change the accelerator key 
combination from there. However, it does not seem to accept the Delete key. 
Shortcomming of GTK?

Under GTK 2.0, you can set the Delete key just like any other shortcut.  I thought Alan was changing these things, but I don't see the change.

Really? Which version? I'm pretty sure there still is code in
GTK to make Delete the remove-this-short-cut-key which does
not allow to make Delete a short-cut itself ...

Looking further, see gtk/gtkmenu.c:gtk_menu_key_press()
[This is from the gtk-2-0 branch but I'm pretty sure 
 it'll never change]

  switch (event->keyval)
    {
    case GDK_Delete:
    case GDK_KP_Delete:
    case GDK_BackSpace:
      delete = TRUE;
      break;
    default:
      break;
    }

Setting to NOTABUG. Our at least NotOurBug :-(

In at least 2.0.5, Delete will remove any existing keybinding, but if there's no current keybinding, it will set it to Delete.  At least under Linux.