Semi-supervised learning (SSL) enables the accurate segmentation of medical images with limited available labeled data. However, its performance usually lags fully supervised methods that require the whole dataset to be labeled. We propose a novel SSL framework that narrows the gap between SSL and fully supervised approaches significantly, while using less than a quarter of labeled data. Our approach is driven by a knowledge exchange process between two networks based on a novel certainty-guided contrastive learning strategy that mitigates the impact of inaccurate pseudo labels and of class imbalance. Building on these, we employ a cross supervised contrastive learning across multiple scales that is able to learn hierarchical features reflecting interrelationships both within and across slices and cases. The computational efficiency of our contrastive learning is boosted by novel sampling strategies that select few representative samples for contrasting, as well as a negative memory bank that increases diversity and eliminates the dependence on batch size. We perform an extensive evaluation on three challenging benchmarks, and the experimental results show that our approach achieves state-ofthe art results. We also show it yields improved accuracy when combined with diverse SSL frameworks, and conduct a detailed ablation study showing the benefits of different components of our model. Our code will be made available publicly following acceptance.