Если Вам так не нравится вариант с JOIN-ами, то попробуйте использовать 10 систему счисления (пусть немного избыточно, зато будет запас по статусам). Проверка сведется к вычислениям критериев на стороне PHP:
$service = 3; // от 1 до 11
$status = 2; // от 1 до 4
$min = $status * pow(10, $service);
$max = ($status+1) * pow(10, $service);
И последующим запросом к MySQL:
SELECT * FROM `test` WHERE `service` >= $min AND `service` < $max
При этом для производительности надо бы добавить индекс по колонке service:
ALTER TABLE `test` ADD INDEX `test` (`service`)
P.S. возможно что-то не так с формулой $min и max, но сама идея - использовать >, < (или BETWEEN) для проверки нужного разряда.
