If friendship is intended to be symmetrical (i.e. it is not possible for A to be friends with B but not vice-versa) then I would just store the one way relationship with a check constraint ensuring that each relationship can only be represented one way.

Also I would ditch the surrogate id and have a composite PK instead (and possibly a composite unique index also on the reversed columns).

CREATE TABLE Friends
  (
     UserID1 INT NOT NULL REFERENCES Users(UserID),
     UserID2 INT NOT NULL REFERENCES Users(UserID),
     CONSTRAINT CheckOneWay CHECK (UserID1 < UserID2),
     CONSTRAINT PK_Friends_UserID1_UserID2 PRIMARY KEY (UserID1, UserID2),
     CONSTRAINT PK_Friends_UserID2_UserID1 UNIQUE (UserID2, UserID1),
  ) 

You don't say the queries that this makes difficult but you can always create a View

CREATE VIEW Foo
AS
SELECT UserID1,UserID2 
FROM Friends
UNION ALL
SELECT UserID2,UserID1 
FROM Friends

If friendship is intended to be symmetrical (i.e. it is not possible for A to be friends with B but not vice-versa) then I would just store the one way relationship with a check constraint ensuring that each relationship can only be represented one way.

Also I would ditch the surrogate id and have a composite PK instead (and possibly a composite unique index also on the reversed columns).

CREATE TABLE Friends
  (
     UserID1 INT NOT NULL REFERENCES Users(UserID),
     UserID2 INT NOT NULL REFERENCES Users(UserID),
     CONSTRAINT CheckOneWay CHECK (UserID1 < UserID2),
     CONSTRAINT PK_Friends_UserID1_UserID2 PRIMARY KEY (UserID1, UserID2),
     CONSTRAINT UQ_Friends_UserID2_UserID1 UNIQUE (UserID2, UserID1)
  ) 

You don't say the queries that this makes difficult but you can always create a View

CREATE VIEW Foo
AS
SELECT UserID1,UserID2 
FROM Friends
UNION ALL
SELECT UserID2,UserID1 
FROM Friends