I think you might be over thinking this a little bit. category security is exactly how i would approach this initially without tags.
i would set the classified ads category security to everyone can see and set the buy and sell category security to everyone can create/reply/see.
regarding visibility of topics on classified ads, users would still be able to see topics in both sub-categories displayed and would also have a clear picture of how the sub-categories are related.
now to address tags:
i know you dont want to use tags, but for your use-case, its a very practical and simple solution. simply have only the classified ads category and instead of making buy and sell sub-categories, make them applicable tags. this mitigates conflicts with category security and visibility that you have outlined above, and makes it even easier to just simply add another tag (hire/service) in the future.