Created Check Constraint WITH NOCHECK - still trusted I needed to alter the conditions of existing constraint - so I dropped it and recreated with the new conditions.

This failed, because there were 800k+ rows, that didn't meet the condition. That strikes me as odd, because 

SELECT * FROM sys.[check_constraints] cc


showed is_not_trusted as 0

Anyway, I recreated the constraint again, this time with hint WITH NOCHECK
This time it passed and I expected is_not_trusted to be 1, but it is still trusted. 

Can someone explain it to me?

My code:

ALTER TABLE dbo.MyTable   
DROP CONSTRAINT CK_MyTable;  
GO  

ALTER TABLE dbo.MyTable WITH NOCHECK
ADD CONSTRAINT CK_MyTable 
CHECK
(
    -- 7 conditions, mainly checking null and not null

)
This might not be an accepted answer and I am ok with that but I cannot put the whole thing in a comment.

I tested your scenario with SQL Server 2016, SP2 and SQL Server 2017 CU9. In both cases I get expected result for is_not_trusted column value. Meaning 1 while using WITH NOCHECK and 0 while using `WITH CHECK'

Here is my test code. Some of the code I used is from Search Engine Q&amp;A #9: How to update constraints? written by Paul Randal.

DROP DATABASE IF EXISTS checkConstraints;
CREATE DATABASE checkConstraints;
GO

USE [checkConstraints]
GO

DROP TABLE IF EXISTS dbo.Sales;
CREATE TABLE dbo.Sales (salesID INT IDENTITY, SalesDate DATETIME);
GO

CREATE CLUSTERED INDEX Sales_CL ON Sales (SalesID);
CREATE NONCLUSTERED INDEX Sales_NCL ON Sales (SalesDate);
GO

SET NOCOUNT ON;
GO

DECLARE @a INT;
SELECT @a = 1;
WHILE (@a &lt; 1000)
BEGIN

INSERT INTO Sales VALUES (GETDATE ());
SELECT @a = @a + 1;

END;
GO

ALTER TABLE Sales DROP CONSTRAINT IF EXISTS  [CK_Sales_nocheck];
GO
ALTER TABLE Sales WITH NOCHECK ADD CONSTRAINT [CK_Sales_nocheck] CHECK (YEAR (SalesDate) &gt;= 2005 AND YEAR (SalesDate) &lt; 2008);
GO

ALTER TABLE Sales DROP CONSTRAINT IF EXISTS [CK_Sales_check];
GO
ALTER TABLE Sales WITH CHECK ADD CONSTRAINT [CK_Sales_check] CHECK (YEAR (SalesDate) &gt;= 2005 AND YEAR (SalesDate) &lt; 2019);
GO

SELECT name, is_not_trusted FROM sys.check_constraints;
GO


Result I get is following: