Вы действительно можете использовать союз, почему бы и нет? Но зачем использовать UNION ALL, а не только UNION? Просто выберите один общий столбец:
SELECT 1
FROM
(select A.fk from A inner join C on A.FK = C.pk
UNION
select B.fk from B inner join C on B.FK = C.pk) AS bothTables
WHERE fk = 'desiredValue';
Это будет работать просто замечательно.
Протестировано на следующих таблицах в MySQL, с myValue = 1, просто для проверки.
mysql> select * from A;
+------+--------+------+
| pk | value | fk |
+------+--------+------+
| 1 | ape | 2 |
| 2 | fjfjfj | 3 |
+------+--------+------+
2 rows in set (0.00 sec)
mysql> select * from B;
+------+--------+------+
| pk | value | fk |
+------+--------+------+
| 1 | katt | 1 |
| 2 | fjfjfj | 3 |
+------+--------+------+
2 rows in set (0.00 sec)
mysql> select * from C;
+------+-------+
| pk | value |
+------+-------+
| 1 | hei |
| 2 | nei |
| 3 | jeg |
+------+-------+
3 rows in set (0.00 sec)