Just found the problem. Posting it here since the behavior is kind of interesting and other people might have the same problem.

The problem was the following:
OrderService is an interface - the mocking here was correct. But the implementation OrderServiceImpl was also mocked:

@Mock private OrderService orderService;
@Mock private OrderServiceImpl orderServiceImpl;

The names of the variables in my case were not as obvious as above so I overlooked it. After removing the Mock of the implementation, it works exactly as it should.

Interesting to me that there is no warning by Mockito when you mock an interface and the implementation for it. Also interesting that it sometimes worked and sometimes didn't - that made it really difficult to analyze.

Thanks for the comments which helped me finding the solution.