I eventually figured it out.
There are two issues involved:
(1) mercurial-server uses the mercurial-API. So one needs to make sure that the PYTHONPATH points at the correct mercurial-folder. As one does this through ssh, one needs to specify the PYTHONPATH in ~hg/.ssh/environment.
(2) Also, there is a hook that modifies the ~hg/.ssh/authorized_keys when one pushes the hgadmin repository. Here, mercurial is run as an executable. You can fix this in /usr/local/share/mercurial-server/init/hgadmin-hgrc by specifying the full path in the lines
changegroup.aaaab_update = hg update -C default > /dev/null
changegroup.aaaac_purge = hg purge --all > /dev/null
I hope that may help somebody who runs into the same problem.