Central government policy departments need to collaborate with executive agencies to provide IT-based services to society. These collaborations are complicated by the fact that the executive agencies are controlled by different ministerial hierarchies, resulting in conflicting interests. Yet, a detailed analysis of these challenges is lacking in the literature. In this paper, we analyze the challenges at several ministries through interviews focused on specific cases as well as interviews focused on expert knowledge. We identified the challenge themes and compared them with the literature, finding several new challenges in practice, including restricted procurement, a Goldilocks zone for escalation, the inability to hold an agent ultimately accountable, and the low priority the central government policy departments give to the implementation. Paradoxically, central government policy departments, as principals, are less powerful and highly dependent on executive agencies instead of the other way around, as suggested by principal-agent theory. These findings imply that there is a need for new governance mechanisms able to deal with all the challenges encountered. The overview of the challenges can serve as a sound foundation for conducting further research into cross-ministerial governance.