It gets activated via dbus. 

Do you have /usr/share/dbus-1/services/org.freedesktop.Notifications.service ?

Does calling the notify-send commandline utility start the daemon ?

I have that file - but calling notify-send does not start the daemon (nor does
it display a notification - unless I have manually started the daemon first).

[maxx@ice ~]$ cat /usr/share/dbus-1/services/org.freedesktop.Notifications.service 
[D-BUS Service]
Name=org.freedesktop.Notifications
Exec=/usr/libexec/notification-daemon

I have constructed a small python test-app:

[maxx@ice src]$ cat test2.py
import pynotify
pynotify.init("foo")
n = pynotify.Notification("foo bar baz")
n.show()

When I run this I get the following error (not sure it helps you any):

[maxx@ice src]$ python test2.py 
Traceback (most recent call last):
  File "test2.py", line 4, in <module>
    n.show()
gobject.GError: Failed to execute program
/usr/local/libexec/notification-daemon: Success

It works fine if I manually start the daemon first.

why is dbus trying to execute a different program than the one in the service file 

/usr/local/libexec/notification-daemon != /usr/libexec/notification-daemon 

?

Self-compiled dbus, maybe ?

No, nothing is self-compiled (except for a version of avant-window-navigator
installed in /usr/local)

Are there any ways to get more logging out of the dbus activation system?

Based on the date this bug was created, it appears to have been reported
during the development of Fedora 8. In order to refocus our efforts as
a project we are changing the version of this bug to '8'.

If this bug still exists in rawhide, please change the version back to
rawhide.
(If you're unable to change the bug's version, add a comment to the bug
and someone will change it for you.)

Thanks for your help and we apologize for the interruption.

The process we're following is outlined here:
http://fedoraproject.org/wiki/BugZappers/F9CleanUp

We will be following the process here:
http://fedoraproject.org/wiki/BugZappers/HouseKeeping to ensure this
doesn't happen again.

This message is a reminder that Fedora 8 is nearing its end of life.
Approximately 30 (thirty) days from now Fedora will stop maintaining
and issuing updates for Fedora 8.  It is Fedora's policy to close all
bug reports from releases that are no longer maintained.  At that time
this bug will be closed as WONTFIX if it remains open with a Fedora 
'version' of '8'.

Package Maintainer: If you wish for this bug to remain open because you
plan to fix it in a currently maintained version, simply change the 'version' 
to a later Fedora version prior to Fedora 8's end of life.

Bug Reporter: Thank you for reporting this issue and we are sorry that 
we may not be able to fix it before Fedora 8 is end of life.  If you 
would still like to see this bug fixed and are able to reproduce it 
against a later version of Fedora please change the 'version' of this 
bug to the applicable version.  If you are unable to change the version, 
please add a comment here and someone will do it for you.

Although we aim to fix as many bugs as possible during every release's 
lifetime, sometimes those efforts are overtaken by events.  Often a 
more recent Fedora release includes newer upstream software that fixes 
bugs or makes them obsolete.

The process we are following is described here: 
http://fedoraproject.org/wiki/BugZappers/HouseKeeping

Fedora 8 changed to end-of-life (EOL) status on 2009-01-07. Fedora 8 is 
no longer maintained, which means that it will not receive any further 
security or bug fix updates. As a result we are closing this bug.

If you can reproduce this bug against a currently maintained version of 
Fedora please feel free to reopen this bug against that version.

Thank you for reporting this bug and we are sorry it could not be fixed.