Sorry for the noise folks, I managed to fix it by using the current libnotify SVN revision.

Quoting their changelog:

* Fixed a bug where a notification's ID could be reset when a different notification was closed. Patch by jylefort. (Bug #94)