How this simple Stored Procedure ended up in Deadlock
Instead of checking to see if the data already exists and then doing an INSERT, try doing an INSERT IGNORE and seeing if the LAST_INSERT_ID() came back with the same value or not on two calls.

CREATE PROCEDURE sp_CreateCtrMsgTagIfNotExist
(
    siteId INT, logTimestamp DATETIME, IntervalId INT,
    digestMatched TINYINT(1), OUT returnpk INT
)
BEGIN

   DECLARE rpk INT;

   SELECT LAST_INSERT_ID() INTO rpk;
   START TRANSACTION;       
   INSERT IGNORE INTO Site_Msg_Tag
       (Site_Msg_Tag_Id,Unit_Id,Log_Timestamp,Interval_Id,Digest_Matched)
       VALUES (NULL,siteId,logTimestamp,IntervalId,digestMatched);
   SELECT LAST_INSERT_ID() INTO returnpk;
   IF returnpk = rpk THEN /*1*/
       SELECT Site_Msg_Tag_Id INTO rpk FROM Site_Msg_Tag
       WHERE Unit_Id = siteId AND Log_Timestamp = logTimestamp
       AND Interval_Id = IntervalId ;
       SET returnpk = 0 - rpk;
   END IF;/*1*/
   COMMIT;

END;


Checking LAST_INSERT_ID()


If two calls produced different values, you should make the stored procedure set returnpk as is to indicate that the row was newly inserted.
If two calls produced the same value, then go query for the Site_Msg_Tag_Id. You should make the stored procedure set returnpk as negative to let you know the Site_Msg_Tag_Id was already there.


Give it a Try !!!