Your query using the CHECKSUM index is incorrect:

SELECT *

FROM dbo.PostalCode

WHERE PostalCheckSum = CHECKSUM(@PostalArea, @PostalCity, @PostalState);

As previously mentioned, the value returned from CHECKSUM will not be unique for the inputs. The same input will always produce the same output, but different input is not guaranteed to produce different output.

Therefore, your query still needs to test the other columns:

SELECT *

FROM dbo.PostalCode

WHERE PostalCheckSum = CHECKSUM(@PostalArea, @PostalCity, @PostalState)

AND PostalArea = @PostalArea

AND PostalCity = @PostalCity

AND PostalState = @PostalState;