La tua idea originaria è PERFETTA per quanto riguarda le regole di normalizzazione dei db.
Effettivamente hai il problema che scrivere ancona-macerata e macerata-ancona è ridondante. Le soluzioni possibili sono due:

1) eviti di duplicare le righe, controllando ad esempio prima di inserire 1-4 che non esista già 4-1. Però quando poi vai a cercare le province confinanti di ciascuna devi fare la ricerca sia sulla prima colonna che sulla seconda

2) ti rassegni ad avere le righe doppie e semplifichi l'accesso