¿Mysql Inner se une con la condición OR?

Puedes unirte en la location_distance tabla dos veces usando un LEFT JOIN y luego use COALESCE() función para devolver el valor correcto para la 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 con demostración

Esto devuelve el 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 |