I solved my problem!
After setting up a fresh system, the shutdown problems appeared again.
I am running Debian Xfce and initially I used slim desktop manager. Now there seems to be a problem with consolekit (in recent Xfce) when slim or xdm are used, whereas this problem apparently does not occur with lightdm, gdm or kdm. https://bbs.archlinux.org/viewtopic.php?id=115507
is one of the threads on this issue.
What helped me, was to install lightdm and purge and completely remove slim.
Now (so far) everything is fine!