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.
That one simple addition made pre-9.0 NOTIFY and post-9.0 NOTIFY completely different beasts.