I'll agree to stand corrected if and only if I can also require that there is a unique constraint across all columns.

Unique constraints like the sort you mean are normally handled through the creation of unique indexes on the columns involved. A properly designed table should forbid the insertion of bad data, either through column level constraints, row level constraints, unique indexes or triggers.

Simply think that providing a primary key may satisfy that constraint but they miss that it may violate 3NF

The tables violated normalization prior to adding the index, all the index does is allow you to deal with the fact, something that you can't do very well without it. If you could explain why that table makes more sense without the id column than with it then you might have a case, but I dont think you can.