Before I picked up the Ramnode server I was using BuddyNS as my primary with the prgmr node as the stealth primary. It worked fine but it was less straightforward than I wanted.
I say "noticeable issues", because although my DNS is monitored, the monitoring isn't granular enough to detect sub-minute outages, for example.
Did you have any issues in particular with the stealth primary solution?
DNS NOTIFY is standardised in: https://tools.ietf.org/rfc/rfc1996.txt
BIND 8+ supports it by default, according to http://docstore.mik.ua/orelly/networking_2ndEd/dns/ch10_03.h...
There is a perl script to achieve the same thing in djbdns, according to http://www.fefe.de/djbdns/#notify (which joe_bleau alluded to).