SQL Server 2019

By using db<>fiddle, you agree to license everything you submit by Creative Commons CC0.

CREATE TABLE [User] (
  id int PRIMARY KEY,
  company_id int,
  UNIQUE (company_id, id)
);

CREATE TABLE UserPair (
  company_id int,
  user1_id int,
  user2_id int,
  PRIMARY KEY (company_id, user1_id, user2_id),
  FOREIGN KEY (company_id, user1_id) REFERENCES [User] (company_id, id),
  FOREIGN KEY (company_id, user2_id) REFERENCES [User] (company_id, id)
);
INSERT [User] (id, company_id) VALUES
(1,1),
(2,1),
(3,2);
3 rows affected

INSERT UserPair (company_id, user1_id, user2_id) VALUES(1,1,2);
1 rows affected

INSERT UserPair (company_id, user1_id, user2_id) VALUES(1,1,3);
Msg 547 Level 16 State 0 Line 1
The INSERT statement conflicted with the FOREIGN KEY constraint "FK__UserPair__286302EC". The conflict occurred in database "fiddle_f9ccded0134b4b60a212d758030b902a", table "dbo.User".
Msg 3621 Level 0 State 0 Line 1
The statement has been terminated.