So it must be something in the authorization / security realm, isn't it? Thus we tried a smart thing and moved that particular function to another - APEX Authenticated - application, while sharing the login credentials via a cookie. But to no avail. Some complaint.
So I contacted the APEX Development team and - as always - I got a quick reply. It wasn't a bug. It's a feature. They explained that you can only use functionality that needs APEX Admin privileges if you are authenticated against the APEX Repository. An - accidental (?) - match on usernames is not enough to grant ADMIN privileges. And that totally makes sense....
So although it was unexpected behaviour, it is the correct behaviour!
BTW. the solution is to create a separate job that runs using the right privileges.