Receiving several deadlocks with simple queries when ran concurrently from different nodes
I would use an UPDATE with an OUTPUT instead of two completely separate statements. 

ALTER PROCEDURE dbo.getnextsessionID
  @id varchar(15) OUTPUT
AS
BEGIN
  SET NOCOUNT ON;

  DECLARE @t TABLE(id varchar(15));

  ;WITH NextID AS 
  (
    SELECT TOP (1) sessionID,used
      FROM dbo.uniqueids 
      WHERE used = 0
      ORDER BY ID
  )
  UPDATE NextID SET used = 1 
    OUTPUT deleted.sessionID INTO @t;

  SELECT @id = RTRIM(LTRIM(id)) FROM @t;
END
GO


Also if the table is large (and as the set where used = 1 grows), I might suggest a filtered index instead, simply because it's much cheaper to maintain:

CREATE INDEX session_used 
  ON dbo.uniqueids(ID, sessionID, used) 
  WHERE used = 0
  WITH (DROP_EXISTING = ON);