MSG 666 when running an insert query on 80M-row indexed table
The low selectivity issue mentioned by Remus is not sufficient on its own to cause the problem on that size table. 

The uniqueifier starts at 1 and can go up to 2,147,483,646 before actually overflowing the range.

It also requires the right pattern of repeated deletes and inserts to see the issue.

CREATE TABLE T
(
X SMALLINT,
Y INT IDENTITY PRIMARY KEY NONCLUSTERED
)

CREATE CLUSTERED INDEX IX ON T(X)

INSERT INTO T VALUES (1),(1),(1),(2),(2)


Gives

+---+---+-------------+
| X | Y | Uniqueifier |
+---+---+-------------+
| 1 | 1 |             |
| 1 | 2 |           1 |
| 1 | 3 |           2 |
| 2 | 4 |             |
| 2 | 5 |           1 |
+---+---+-------------+


Then running

DELETE FROM T 
WHERE Y IN (2,3)

INSERT INTO T VALUES (1),(1)


Gives

+---+---+-------------+
| X | Y | Uniqueifier |
+---+---+-------------+
| 1 | 1 |             |
| 1 | 6 |           3 |
| 1 | 7 |           4 |
| 2 | 4 |             |
| 2 | 5 |           1 |
+---+---+-------------+


Showing in that case the uniqueifier did not reuse the values from the deleted rows.

However then running

DELETE FROM T 
WHERE Y IN (6,7)
WAITFOR DELAY '00:00:10'
INSERT INTO T VALUES (1),(1)


Gives

+---+---+-------------+
| X | Y | Uniqueifier |
+---+---+-------------+
| 1 | 1 |             |
| 1 | 8 |           1 |
| 1 | 9 |           2 |
| 2 | 4 |             |
| 2 | 5 |           1 |
+---+---+-------------+


Showing that the high water mark can be reset after deleting the duplicate with the highest uniqueifier value. The delay was to allow the ghost record cleanup process to run.

Because life is too short to insert 2 billion duplicates I then used DBCC WRITEPAGE to manually adjust the highest uniqueifier to 2,147,483,644



I then ran

INSERT INTO T VALUES (1)


multiple times. It succeeded twice and failed on the third attempt with error 666.

This was actually one lower than I would have assumed. Meaning that the highest uniqueifier inserted was 2,147,483,646 rather than the maximum int size of 2,147,483,647