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