I've had this problem myself. As well as the mechanical issues with mulch (large air pockets, etc.) and possible allopathic interactions, I've heard that some plants just need contact with mineral soil to get started.
Also, carrots, parsnips, lettuce, etc. are early successional plants with small, windblown seeds. It would make sense that they would do best in bare, disturbed soil.
Can you scrap back the mulch and plant them in a row of soil at the bottom of the trench, then push the mulch back together?
I tried putting a strip of
compost in the mulch, but that dried out too fast.
I've now moved over to minimal tillage, but I still have problems with small seeds because they dry out so fast in Colorado.