What type of database can I use to store mutual scores between every combination of users?
Because I could look up either user, I have to store the pairings "both ways" 


Well, that's not true. You could normalize the data because the relations aren't directed anyway.

CREATE TABLE scores (
  user_id   int,
  friend_id int,
  score     int,
  CHECK ( user_id &lt; friend_id ),
  PRIMARY KEY (user_id, friend_id)
);

INSERT INTO scores (user_id, friend_id,score)
VALUES
  ( 1, 2, 15.2 ),
  ( 1, 3, 19.7 ),
  ( 2, 3, 21.0 );


Now you can find the relation easy.

SELECT *
FROM scores
WHERE user_id = 1
  AND friend_id = 2;


If you don't want to put the rule in the app, just rewrite the query into.

SELECT *
FROM scores
WHERE (user_id, friend_id) =
  ROW( least(1,2), greatest(1,2) );