I have successfully used notifications on 2 Drupal 6 sites. I like it. Subscriptions had a good reputation but Notifications looked to be more modular and extensible; however, what tipped me towards notifications was the fact that it seemed that the Organic Groups developers were keen to support it and I was looking at putting OG onto my sites (which I subsequently did)
I have the 6.x.2 version of notifications, which seems stable and does what I want. Very limited experience of the 6.x.4 version suggested it was not stable so I did not persist with that and it remains in beta after 2 years.
Now I have recently been involved in the development of a Drupal 7 site. Although it is over 18 months since D7 was released there is no full Notifications version yet and the module is flagged as Seeking new developer and has been for a significant length of time. Apparently a quick upgrade was done when Dr7 was released with some limited functionality (what though?) and there is an Alpha2 version which seems to have been receiving some considerable attention (but last updated June).
On this basis, you might be safer to go with Subscriptions which now has a full Dr7 release if you have any thoughts of migrating to Dr7 or developing other sites that might use Dr7. That is mainly to avoid the difficulties in mastering two admin UIs and to protect you in case Notifications really is moribund.
Subscriptions is in the hands of a very experienced developer who has been maintaining it for a long time.
Please note that I have not done a systematic comparison of Subscriptions and Notifications for Dr6 though I did spend quite a while investigating the two at one time several years ago. See my contribution here:
(This contains contributions by many others and is useful for an insight into the position in 2008! But Subscriptions and Notifications will both have been enhanced since those posts were written).