SQL Server 2014 Concurrent input issue
Community wiki answer:

MERGE has some issues you should be aware of, see Use Caution with SQL Server's MERGE Statement by Aaron Bertrand.

More specifically to your present situation, MERGE provides no additional protection against concurrency issues beyond an automatic containing transaction. You would need to add a SERIALIZABLE hint (or its synonym, HOLDLOCK) to the MERGE statement as well, see “UPSERT” Race Condition With MERGE by Dan Guzman. Note that an UPDLOCK hint is not necessary with MERGE.

For a more general overview of the issues and options, see the following by Michael J. Swart:


SQL Server UPSERT Patterns and Antipatterns
Mythbusting: Concurrent Update/Insert Solutions


A popular and robust solution is to add a WITH (UPDLOCK, SERIALIZABLE) hint to table access in the NOT EXISTS check, with a containing transaction around the whole UPSERT operation.

Using your example:

BEGIN TRANSACTION;

IF NOT EXISTS
(
    SELECT * 
    FROM Orders WITH (UPDLOCK, SERIALIZABLE)
    WHERE OrderLineID=@OrderLineID
)
    INSERT INTO Orders () VALUES ()
ELSE
    UPDATE Orders 
    SET ... 
    WHERE OrderLineID=@OrderLineID 
    AND LastModified&lt;@CreatedTime;

COMMIT TRANSACTION;


Or equally:

BEGIN TRANSACTION;

INSERT INTO Orders ()
SELECT ...
WHERE NOT EXISTS
(
    SELECT * 
    FROM Orders WITH (UPDLOCK, SERIALIZABLE)
    WHERE OrderLineID=@OrderLineID
);

IF @@ROWCOUNT = 0
BEGIN
    UPDATE Orders 
    SET ... 
    WHERE OrderLineID=@OrderLineID 
    AND LastModified&lt;@CreatedTime;
END;

COMMIT TRANSACTION;


The order of the INSERT and UPDATE operations can be switched so that whichever you expect to succeed most often is tried first. The hints must always be applied to the first operation.

For example, if updates are expected to be most numerous:

BEGIN TRANSACTION;

UPDATE Orders WITH (UPDLOCK, SERIALIZABLE)
SET ... 
WHERE OrderLineID=@OrderLineID 
AND LastModified&lt;@CreatedTime;

IF @@ROWCOUNT = 0
BEGIN
    INSERT INTO Orders ()
    SELECT ...
END;

COMMIT TRANSACTION;


The uniqueness constraint mentioned in the question is a good idea for consistency in general, but not strictly needed for the methods noted here. If you were to use Michael Swart's Just Do It pattern, a uniqueness guarantee would be required for correct operation.

As a reminder, if you prefer MERGE for whatever reason, you must use a SERIALIZABLE hint against the target table.

While it is true in general that locking hints should be avoided as far as possible, this is one example of a valid use case.