What are some efficient ways in using COUNT(*) with WHERE
SET NOCOUNT has nothing to do with your ability to perform counts or the efficiency of doing so.  This setting merely enables the reporting of affected rowcounts to the client (e.g. the n row(s) affected. message in Management Studio). The reason it is recommended to be off is because it is unnecessarily chatty and can break some applications / APIs.

As for getting more efficient counts from complex joins, it's possible that your joins could be made more efficient, but we can't see them. It's also possible that you can pay that cost at a different time by using filtered indexes, indexed views, or pre-aggregating yourself at insert/update time, using a trigger, etc. Sometimes this can pay off but other than a general suggestion there's not much else we'll be able to offer you without a lot more details.