In case anybody else has the same problem, I solved it by turning off billboarding and manually rotating the sprites to face the camera. For my game that just means rotation around the x-axis -45° so easy peasy. That made the z-indexing work as expected.
Hope that helps some one!