Como na minha tabela atualmente tenho apenas cerca de 5k linhas e elas estão crescendo lentamente, decidi usar a seguinte abordagem simples (ela veio a mim logo depois que escrevi a pergunta).
A semente, digamos, é Honda Accord (model_id 456), 2004, gasolina, 2.0L, 155hp, sedan com ID auto-inc 123.
SELECT vehicles.*,
(IF(`fuel_type`='gasoline', 3, 0) +
IF(`body_style`='sedan', 1, 0) +
IF(`year` > 2001 AND `year` < 2007, 2, 0) +
IF(`engine_size` >= 1.8 AND `engine_size` <= 2.2, 1, 0) +
IF(`engine_power`=155, 3, IF(`engine_power`>124 AND `engine_power`<186, 1, 0))) AS `rank`
FROM vehicles
WHERE vehicle_id!=123 AND model_id=456
ORDER BY `rank` DESC
LIMIT 3
Vai funcionar, desde que eu não faça muitas linhas. Se a tabela se tornar 50-100k, provavelmente terei que mudar para algo como
Lucene ? 
