NOTIFY is transaction-safe: if the NOTIFY-ing transaction rolls back, the NOTIFY will not be delivered. See the discussion here ("NOTIFY interacts with SQL transactions in some important ways..."):
Yup, my bad, thanks. I confused the two problems I worked through in working through my use case. The transaction safety one was not the NOTIFY version of the project. That had different issues, which I need to go back and look at my notes for. My memory is a bit hazy, but IIRC we were seeing notifications dropped under high velocities and needed delivery guarantees.
I seem to remember that when it was first implemented there was a fairly small buffer for queued messages. That might have contributed to your problem. The docs say it's 8GB by default now, which is probably sufficient.
https://www.postgresql.org/docs/9.6/static/sql-notify.html