The whole point of that "CarrierTrackingNumber = ISNULL(@Carrier, CarrierTrackingNumber)" predicate is to provide a way of turning off the filter by passing @Carrier a NULL. It's not to look for NULL values, it's to allow a single stored procedure to support various combinations of search parameters.

Unfortunately, the stored procedure developer was lazy - the CarrierTrackingNumber that is the second parameter to the ISNULL will change from row to row, thus ensuring the equality always matches when @Carrier IS NULL (unless CarrierTrackingNumber happens to be NULL, in which case that row will be filtered out since NULL = NULL is Unknown). Any time you manipulate a field, left or right side of the operator, you pretty much guarantee that your predicate is no longer SARGable.

A better way to rewrite that predicate is "(CarrierTrackingNumber = @Carrier OR @Carrier IS NULL)". The problem is that then the query optimizer still can't rely on the predicate unless you use "OPTION (RECOMPILE)". If you use the latter, than the optimizer is allowed to look at the value of @Carrier and use that it designing the query plan. If @Carrier is NULL, it knows there is no need to check CarrierTrackingNumber = @Carrier and will design an appropriate plan (i.e. only using the first parameter in the Seek Predicate and using the third as a normal Predicate). If @Carrier is not NULL, it knows that it can safely use @Carrier in the Seek Predicate. But if you don't use "OPTION (RECOMPILE)", it has to assume either case is possible, and thus it can't use @Carrier in the Seek Predicate.

But "OPTION (RECOMPILE)" means every call gets recompiled - yuck! My personal experience is that if you want good behavior out of these sorts of stored procedures, provide explicit queries for the common use cases gated by testing the passed parameters for NULL. At the end, you can cover all the uncommon cases with a single query that tests all the parameters like above and uses "OPTION (RECOMPILE)". Recompiling isn't the best approach, but it still usually beats a clustered index scan!

Personally, I'd really like to see Microsoft implement Skip Scanning of indexes. See https://connect.microsoft.com/SQLServer/feedback/details/695044/implement-index-skip-scan .