Encontrei uma solução funcional para o problema acima e estou postando aqui, caso alguém mais tenha um problema semelhante.
A solução é usar uma sub-seleção, em vez de uma instrução case. Aqui está a divisão de código acima, corrigida. (Não sei se esta é a melhor ou mais eficiente solução, mas resolveu o problema para mim, por enquanto, e parece retornar os resultados da pesquisa razoavelmente rapidamente.)
SELECT
exercises.ID AS ID,
exercises.title AS title,
(
(
SELECT COUNT(1)
FROM searchtags
LEFT JOIN exerciseSearchtags
ON exerciseSearchtags.searchtagID = searchtags.ID
WHERE searchtags.title LIKE CONCAT('%',?,'%')
AND exerciseSearchtags.exerciseID = exercises.ID
)+
(
SELECT COUNT(1)
FROM searchtags
LEFT JOIN exerciseSearchtags
ON exerciseSearchtags.searchtagID = searchtags.ID
WHERE searchtags.title LIKE CONCAT('%',?,'%')
AND exerciseSearchtags.exerciseID = exercises.ID
)+
...etc...
(
SELECT COUNT(1)
FROM searchtags
LEFT JOIN exerciseSearchtags
ON exerciseSearchtags.searchtagID = searchtags.ID
WHERE searchtags.title LIKE CONCAT('%',?,'%')
AND exerciseSearchtags.exerciseID = exercises.ID
)
) AS relevance
FROM
exercises
LEFT JOIN exerciseSearchtags
ON exerciseSearchtags.exerciseID = exercises.ID
LEFT JOIN searchtags
ON searchtags.ID = exerciseSearchtags.searchtagID
WHERE
searchtags.title LIKE CONCAT('%',?,'%') OR
searchtags.title LIKE CONCAT('%',?,'%') OR
...etc...
searchtags.title LIKE CONCAT('%',?,'%')
GROUP BY
exercises.ID
ORDER BY
relevance DESC