Muy pocas opciones, me temo.
Siempre tiene que tocar la tabla dos veces, ya sea CONTAR, EXISTE antes, EXISTE en UNION, cláusula TOP, etc.
select
id, category
from mytable
where category = @category
union all --edit, of course it's quicker
select
0, ''
where NOT EXISTS (SELECT * FROM mytable where category = @category)
Una solución EXISTE es mejor que CUENTA porque se detendrá cuando encuentre una fila. COUNT recorrerá todas las filas para contarlas