This approach works for me, but once an item is chosen, the cell shows a little red triangle in the upper right corner. Hovering over it shows "Invalid: input must fall within specified range".

Ideally, the dropdown list would be the one with used items removed but the valid list would be the original list. I'm not sure if that is possible.