Uma única instrução do SQL Server é atômica e consistente?

Eu tenho operado sob a suposição de que uma única instrução no SQL Server é consistente

Essa suposição está errada. As duas transações a seguir têm semântica de bloqueio idêntica:

STATEMENT

BEGIN TRAN; STATEMENT; COMMIT

Nenhuma diferença. Declarações únicas e auto-commits não mudam nada.

Portanto, mesclar toda a lógica em uma instrução não ajuda (se ajudou, foi por acidente porque o plano mudou).

Vamos resolver o problema em mãos. SERIALIZABLE corrigirá a inconsistência que você está vendo porque garante que suas transações se comportem como se fossem executadas em um único thread. De forma equivalente, eles se comportam como se fossem executados instantaneamente.

Você estará recebendo impasses. Se você estiver de acordo com um loop de repetição, você terminou neste ponto.

Se você quiser investir mais tempo, aplique dicas de bloqueio para forçar o acesso exclusivo aos dados relevantes:

UPDATE Gifts  -- U-locked anyway
SET GivenAway = 1
WHERE GiftID = (
   SELECT TOP 1 GiftID
   FROM Gifts WITH (UPDLOCK, HOLDLOCK) --this normally just S-locks.
   WHERE g2.GivenAway = 0
    AND (SELECT COUNT(*) FROM Gifts g2 WITH (UPDLOCK, HOLDLOCK) WHERE g2.GivenAway = 1) < 5
   ORDER BY g2.GiftValue DESC
)

Agora você verá a simultaneidade reduzida. Isso pode ser totalmente bom, dependendo da sua carga.

A própria natureza do seu problema dificulta a obtenção de simultaneidade. Se você precisar de uma solução para isso, precisaremos aplicar técnicas mais invasivas.

Você pode simplificar um pouco o UPDATE:

WITH g AS (
   SELECT TOP 1 Gifts.*
   FROM Gifts
   WHERE g2.GivenAway = 0
    AND (SELECT COUNT(*) FROM Gifts g2 WITH (UPDLOCK, HOLDLOCK) WHERE g2.GivenAway = 1) < 5
   ORDER BY g2.GiftValue DESC
)
UPDATE g  -- U-locked anyway
SET GivenAway = 1

Isso elimina uma junção desnecessária.