Mysql Inner junta-se com condição OR?

Você pode participar na location_distance tabela duas vezes usando um LEFT JOIN e então use o COALESCE() função para retornar o valor correto para a distance :

select ot.id,
  ot.fromlocid,
  ot.tolocid,
  ot.otherdata,
  coalesce(ld1.distance, ld2.distance) distance
from other_table ot
left join location_distance ld1
  on ld1.fromLocid = ot.toLocid
  and ld1.toLocid = ot.fromLocid 
left join location_distance ld2
  on ld2.toLocid = ot.toLocid
  and ld2.fromLocid = ot.fromLocid

Consulte SQL Fiddle with Demo

Isso retorna o resultado:

| ID | FROMLOCID | TOLOCID | OTHERDATA | DISTANCE |
---------------------------------------------------
| 12 |         5 |       3 |      xxxx |       70 |
| 22 |         2 |       4 |      xxxx |       63 |
| 56 |         8 |       6 |      xxxx |       15 |
| 78 |         3 |       5 |      xxxx |       70 |