Como determinar se um registro com tipo de dados IMAGE específico já existe na tabela?

A maneira mais eficaz que consigo pensar é usar uma coluna computada persistente a> para um valor de hash da coluna de imagem. Use hashbytes para calcular o hash e adicionar uma restrição exclusiva na coluna calculada.

Definição da tabela:

create table Images
(
  ID int identity primary key, 
  Img varbinary(max),
  ImgHash as convert(varbinary(16), hashbytes('MD5', Img)) persisted unique
)

Código de exemplo em relação à tabela de imagens:

insert into Images values 
(convert(varbinary(max), 'Image1')),
(convert(varbinary(max), 'Image2'))

declare @NewImage varbinary(max) = convert(varbinary(max), 'Image2')

select count(*)
from Images
where ImgHash = hashbytes('MD5', @NewImage)

A restrição exclusiva cria um índice que será usado na consulta.

Seu SP para adicionar uma imagem pode ficar assim usando merge e saída com um truque desta resposta UPDATE -no-op na instrução SQL MERGE fornecido por Andriy M .

create procedure Images_Add
  @NewImage varbinary(max)
as  

declare @dummy int

merge Images as T
using (select @NewImage, hashbytes('MD5', @NewImage)) as S(Img, ImgHash)
on T.ImgHash = S.ImgHash
when not matched then
  insert(Img) values(S.Img)
when matched then
  update set @dummy = 0  
output inserted.ID;