Hm,
I tested it again by creating a post and then adding the staff tag to it. The watching user can see the post (and the staff tag) in the New and Latest list, but they don’t have any notification in their notification list and no E-Mail was sent.
Am I misunderstanding the concept of watching a tag/category?