Solution 1:

instead of below Code

BEGIN
   INSERT INTO EmailsRecebidos (De, Assunto, Data)
   VALUES (@_DE, @_ASSUNTO, @_DATA)
   WHERE NOT EXISTS ( SELECT * FROM EmailsRecebidos 
                   WHERE De = @_DE
                   AND Assunto = @_ASSUNTO
                   AND Data = @_DATA);
END

replace with

BEGIN
   IF NOT EXISTS (SELECT * FROM EmailsRecebidos 
                   WHERE De = @_DE
                   AND Assunto = @_ASSUNTO
                   AND Data = @_DATA)
   BEGIN
       INSERT INTO EmailsRecebidos (De, Assunto, Data)
       VALUES (@_DE, @_ASSUNTO, @_DATA)
   END
END

Updated : (thanks to @Marc Durdin for pointing)

Note that under high load, this will still sometimes fail, because a second connection can pass the IF NOT EXISTS test before the first connection executes the INSERT, i.e. a race condition. See stackoverflow.com/a/3791506/1836776 for a good answer on why even wrapping in a transaction doesn't solve this.

Solution 2:

For those looking for the fastest way, I recently came across these benchmarks where apparently using "INSERT SELECT... EXCEPT SELECT..." turned out to be the fastest for 50 million records or more.

Here's some sample code from the article (the 3rd block of code was the fastest):

INSERT INTO #table1 (Id, guidd, TimeAdded, ExtraData)
SELECT Id, guidd, TimeAdded, ExtraData
FROM #table2
WHERE NOT EXISTS (Select Id, guidd From #table1 WHERE #table1.id = #table2.id)
-----------------------------------
MERGE #table1 as [Target]
USING  (select Id, guidd, TimeAdded, ExtraData from #table2) as [Source]
(id, guidd, TimeAdded, ExtraData)
    on [Target].id =[Source].id
WHEN NOT MATCHED THEN
    INSERT (id, guidd, TimeAdded, ExtraData)
    VALUES ([Source].id, [Source].guidd, [Source].TimeAdded, [Source].ExtraData);
------------------------------
INSERT INTO #table1 (id, guidd, TimeAdded, ExtraData)
SELECT id, guidd, TimeAdded, ExtraData from #table2
EXCEPT
SELECT id, guidd, TimeAdded, ExtraData from #table1
------------------------------
INSERT INTO #table1 (id, guidd, TimeAdded, ExtraData)
SELECT #table2.id, #table2.guidd, #table2.TimeAdded, #table2.ExtraData
FROM #table2
LEFT JOIN #table1 on #table1.id = #table2.id
WHERE #table1.id is null