Maybe the shortcut is already present in another desktop, maybe you moved it instead of deleting it... Same situation happened to me the other day.

I think you can't have the same shortcut in different desktops... well at least using the ui