Modern DB engines can enforce Unique or PK constraints without indexes. Yes, they perform scans.
So you have to add an index on that column, or start talking about tombstoning data instead of deleting it, but in which case you may still need the FK index to search out references to an old row to replace with a new one.