RecursiveMutex needs task to yield or delay?

This is a contradiction in itself.

Again, my suspicion is that task1 re-aquires the mutex after releasing it so fast that task2 does not have a chance to claim it. Could that be possible?

Can you run your application under control of tracealyzer?