Also, for the working notifications (like notify-send), the notification is drawn with a mix of Gnome3 and unity notification styles. That's quite ugly.
It seems to be caused by notification-daemon, which comes with gnome-flashback (but conflicts with notify-osd?). Unfortunately, the package can't be removed because it is a dependency of gnome-flashback.
Killing the process fixes the notification system, i.e. only notify-osd is used and volume up/down/mute shows a notification again.
In order to prevent the notification-daemon to start at each gnome-fallback session, I edited the file /etc/xdg/autostart/notification-daemon.desktop. I changed the line:
AutostartCondition=GNOME3 unless-session gnome
Note that this is just a workaround. I think a bug report should be filled in launchpad for this, unless it can be fixed without manually editing a file provided by a package.