Как составить запрос?

Думаю разочарую вас.

select  Q.* from devices Q where Q.devices_id not in
(
select B.devices_id 
from    object_categories C 
inner join devices_categories B  on B.categoryId=C.categoryId and C.objectId=@objectId
GROUP BY B.devices_id Having COUNT(*)=(select count(*) from devices_categories Z where Z.objectId=@objectId)
)

P.S. интересно кто минус поставил, вроде у вас все верно

Как составить запрос?

Меня всегда настораживали конструкции

from a,b,c,d where ...

вместо явного join. Среде выполнения остается много возможностей по не оптимальному выполнению кода. Например: слепить cross join и только затем проверять where.

Возможно ли составить такой SQL запрос?

Вы правы. А еще меня настораживает

*, MAX(`f5`) AS `f5`

в сочетание с GROUP BY `f1`, `f2`, `f3`. Не знаю, что будет в MySQL, а в MSSQL ошибка, что f4 и f5 должны участвовать в GROUP BY…