Why did my SQL fail when I added a covering index?

Question

I'm totally confused by this one. I added a covering index to a SQL Server 2017 table and my integration tests broke.

Here is some simple SQL to illustrate the problem:

CREATE TABLE MyColumns (ColumnID INT PRIMARY KEY, LookupCodeTypeID INT)

INSERT INTO MyColumns (ColumnID, LookupCodeTypeID) 
VALUES (18, 37)

CREATE TABLE MyCodes (CodeID INT PRIMARY KEY, CodeTypeID INT, Code NVARCHAR(50), IsDeleted BIT)

INSERT INTO MyCodes (CodeID, CodeTypeID, Code, IsDeleted) 
VALUES (1, 12, 'North', 0), (2, 12, 'South', 0), (19, 37, '0', 0),
       (20, 37, '1', 0), (21, 37, '2', 1), (22, 37, '3', 0)

SELECT CAST(Code AS INT) AS CodeIndex
FROM MyCodes
INNER JOIN MyColumns ON LookupCodeTypeID = CodeTypeID
WHERE ColumnID = 18 AND IsDeleted = 0
ORDER BY CodeIndex

-- This index was created for other reasons but the following SQL broke
CREATE NONCLUSTERED INDEX IX1_MyCodes ON MyCodes (CodeTypeID) INCLUDE (Code)

SELECT CAST(Code AS INT) AS CodeIndex
FROM MyCodes
INNER JOIN MyColumns ON LookupCodeTypeID = CodeTypeID
WHERE ColumnID = 18 AND IsDeleted = 0
ORDER BY CodeIndex

The index was created to solve another problem elsewhere but the failed tests brought me to this code.

From trying to create an example to reproduce the problem I can see that for this code adding IsDeleted to the covering index would solve the problem, but this is not what I was expecting.

Since the tests have highlighted the issue I'll add IsDeleted to the covering index.

My question is WHY did the SQL break and how can I predict what else might break since only some of our code has integration tests?